Submission #2818183
Source Code Expand
#include<bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<n;i++) #define MAX_V 300 int V; using Weight = long double; const Weight INF = 1000000000; // const Weight eps = 1e-8; struct Edge{ int src, dest; int cap, rev; Weight weight; bool operator < (const Edge &rhs) const {return weight > rhs.weight;} }; using Edges = vector<Edge>; using Graph = vector<Edges>; using Array = vector<Weight>; using Matrix = vector<Array>; Weight h[MAX_V]; // potential Weight dist[MAX_V]; // minimum distance int prevv[MAX_V], preve[MAX_V]; // previous vertex and edge void add_edge(Graph &g, int src, int dest, int cap, Weight weight) { g[src].push_back((Edge){src, dest, cap, (int)g[dest].size(), weight}); g[dest].push_back((Edge){dest, src, 0, (int)g[src].size() - 1, -weight}); } Weight min_cost_flow(Graph &g, int s, int t, int f) { Weight res = 0; V = g.size(); memset(h, 0, sizeof(h)); using P = pair<Weight, int>; while (f > 0) { priority_queue<P, vector<P>, greater<P> > que; fill(dist, dist + V, INF); dist[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (dist[v] < p.first) continue; REP(i, g[v].size()) { Edge &e = g[v][i]; if (e.cap > 0 && dist[e.dest] > dist[v] + e.weight + h[v] - h[e.dest] /* + eps */) { dist[e.dest] = dist[v] + e.weight + h[v] - h[e.dest]; prevv[e.dest] = v; preve[e.dest] = i; que.push(P(dist[e.dest], e.dest)); } } } if (dist[t] == INF) return -1; REP(v, V) h[v] += dist[v]; int d = f; for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap); f -= d; res += d * h[t]; for (int v = t; v != s; v = prevv[v]) { Edge &e = g[prevv[v]][preve[v]]; e.cap -= d; g[v][e.rev].cap += d; } } return res; } int main(){ int n; cin>>n; vector<int> x(n); vector<int> y(n); for(int i=0;i<n;i++) cin>>x[i]>>y[i]; Graph g(2*n+3); add_edge(g,2*n+2,2*n+1,1000,0); for(int i=0;i<n;i++){ add_edge(g,2*n,i,1,0); add_edge(g,i+n,2*n+1,1,0); add_edge(g,i,2*n+2,1,2*abs(x[i])); for(int j=0;j<n;j++){ if(i==j) continue; Weight cost=sqrt((x[i]+x[j])*(x[i]+x[j])+(y[i]-y[j])*(y[i]-y[j])); add_edge(g,i,j+n,1,cost); } } cout<<fixed<<setprecision(10); cout<<min_cost_flow(g,2*n,2*n+1,n)/2<<endl; return 0; }
Submission Info
Submission Time | |
---|---|
Task | B - 玉座の間 |
User | nikutto |
Language | C++14 (GCC 5.4.1) |
Score | 50 |
Code Size | 2574 Byte |
Status | WA |
Exec Time | 19 ms |
Memory | 1152 KB |
Judge Result
Set Name | Subtask1 | Subtask2 | Subtask3 | Subtask4 | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 50 / 50 | 0 / 50 | 0 / 50 | 0 / 50 | ||||||||||||||
Status |
|
|
|
|
Set Name | Test Cases |
---|---|
Subtask1 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt |
Subtask2 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt |
Subtask3 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt |
Subtask4 | 11_rand00.txt, 11_rand01.txt, 11_rand02.txt, 11_rand03.txt, 11_rand04.txt, 11_rand05.txt, 11_rand06.txt, 11_rand07.txt, 11_rand08.txt, 11_rand09.txt, 11_rand10.txt, 11_rand11.txt, 11_rand12.txt, 11_rand13.txt, 11_rand14.txt, 11_rand15.txt, 11_rand16.txt, 11_rand17.txt, 11_rand18.txt, 11_rand19.txt, 11_rand20.txt, 11_rand21.txt, 11_rand22.txt, 11_rand23.txt, 11_rand24.txt, 21_rand00.txt, 21_rand01.txt, 21_rand02.txt, 21_rand03.txt, 21_rand04.txt, 21_rand05.txt, 21_rand06.txt, 21_rand07.txt, 21_rand08.txt, 21_rand09.txt, 21_rand10.txt, 21_rand11.txt, 21_rand12.txt, 21_rand13.txt, 21_rand14.txt, 21_rand15.txt, 21_rand16.txt, 21_rand17.txt, 21_rand18.txt, 21_rand19.txt, 21_rand20.txt, 21_rand21.txt, 21_rand22.txt, 21_rand23.txt, 21_rand24.txt, 31_rand00.txt, 31_rand01.txt, 31_rand02.txt, 31_rand03.txt, 31_rand04.txt, 31_rand05.txt, 31_rand06.txt, 31_rand07.txt, 31_rand08.txt, 31_rand09.txt, 31_rand10.txt, 31_rand11.txt, 31_rand12.txt, 31_rand13.txt, 31_rand14.txt, 31_rand15.txt, 31_rand16.txt, 31_rand17.txt, 31_rand18.txt, 31_rand19.txt, 31_rand20.txt, 31_rand21.txt, 31_rand22.txt, 31_rand23.txt, 31_rand24.txt, 41_rand00.txt, 41_rand01.txt, 41_rand02.txt, 41_rand03.txt, 41_rand04.txt, 41_rand05.txt, 41_rand06.txt, 41_rand07.txt, 41_rand08.txt, 41_rand09.txt, 41_rand10.txt, 41_rand11.txt, 41_rand12.txt, 41_rand13.txt, 41_rand14.txt, 41_rand15.txt, 41_rand16.txt, 41_rand17.txt, 41_rand18.txt, 41_rand19.txt, 41_rand20.txt, 41_rand21.txt, 41_rand22.txt, 41_rand23.txt, 41_rand24.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
11_rand00.txt | AC | 1 ms | 256 KB |
11_rand01.txt | AC | 1 ms | 256 KB |
11_rand02.txt | AC | 1 ms | 256 KB |
11_rand03.txt | AC | 1 ms | 256 KB |
11_rand04.txt | AC | 1 ms | 256 KB |
11_rand05.txt | AC | 1 ms | 256 KB |
11_rand06.txt | AC | 1 ms | 256 KB |
11_rand07.txt | AC | 1 ms | 256 KB |
11_rand08.txt | AC | 1 ms | 256 KB |
11_rand09.txt | AC | 1 ms | 256 KB |
11_rand10.txt | AC | 1 ms | 256 KB |
11_rand11.txt | AC | 1 ms | 256 KB |
11_rand12.txt | AC | 1 ms | 256 KB |
11_rand13.txt | AC | 1 ms | 256 KB |
11_rand14.txt | AC | 1 ms | 256 KB |
11_rand15.txt | AC | 1 ms | 256 KB |
11_rand16.txt | AC | 1 ms | 256 KB |
11_rand17.txt | AC | 1 ms | 256 KB |
11_rand18.txt | AC | 1 ms | 256 KB |
11_rand19.txt | AC | 1 ms | 256 KB |
11_rand20.txt | AC | 1 ms | 256 KB |
11_rand21.txt | AC | 1 ms | 256 KB |
11_rand22.txt | AC | 1 ms | 256 KB |
11_rand23.txt | AC | 1 ms | 256 KB |
11_rand24.txt | AC | 1 ms | 256 KB |
21_rand00.txt | WA | 1 ms | 256 KB |
21_rand01.txt | WA | 1 ms | 256 KB |
21_rand02.txt | WA | 1 ms | 256 KB |
21_rand03.txt | WA | 1 ms | 256 KB |
21_rand04.txt | WA | 1 ms | 256 KB |
21_rand05.txt | WA | 1 ms | 256 KB |
21_rand06.txt | AC | 1 ms | 256 KB |
21_rand07.txt | AC | 1 ms | 256 KB |
21_rand08.txt | WA | 1 ms | 256 KB |
21_rand09.txt | WA | 1 ms | 256 KB |
21_rand10.txt | WA | 1 ms | 256 KB |
21_rand11.txt | AC | 1 ms | 256 KB |
21_rand12.txt | AC | 1 ms | 256 KB |
21_rand13.txt | WA | 1 ms | 256 KB |
21_rand14.txt | WA | 1 ms | 256 KB |
21_rand15.txt | WA | 1 ms | 256 KB |
21_rand16.txt | WA | 1 ms | 256 KB |
21_rand17.txt | AC | 1 ms | 256 KB |
21_rand18.txt | WA | 1 ms | 256 KB |
21_rand19.txt | WA | 1 ms | 256 KB |
21_rand20.txt | WA | 1 ms | 256 KB |
21_rand21.txt | WA | 1 ms | 256 KB |
21_rand22.txt | AC | 1 ms | 256 KB |
21_rand23.txt | AC | 1 ms | 256 KB |
21_rand24.txt | AC | 1 ms | 256 KB |
31_rand00.txt | WA | 1 ms | 256 KB |
31_rand01.txt | WA | 1 ms | 256 KB |
31_rand02.txt | WA | 2 ms | 256 KB |
31_rand03.txt | WA | 1 ms | 256 KB |
31_rand04.txt | WA | 1 ms | 256 KB |
31_rand05.txt | WA | 1 ms | 256 KB |
31_rand06.txt | WA | 1 ms | 256 KB |
31_rand07.txt | AC | 1 ms | 256 KB |
31_rand08.txt | WA | 1 ms | 256 KB |
31_rand09.txt | WA | 1 ms | 256 KB |
31_rand10.txt | WA | 1 ms | 256 KB |
31_rand11.txt | WA | 1 ms | 256 KB |
31_rand12.txt | WA | 1 ms | 256 KB |
31_rand13.txt | WA | 1 ms | 256 KB |
31_rand14.txt | WA | 1 ms | 256 KB |
31_rand15.txt | AC | 1 ms | 256 KB |
31_rand16.txt | WA | 1 ms | 256 KB |
31_rand17.txt | WA | 1 ms | 256 KB |
31_rand18.txt | WA | 2 ms | 256 KB |
31_rand19.txt | WA | 2 ms | 256 KB |
31_rand20.txt | WA | 2 ms | 256 KB |
31_rand21.txt | WA | 1 ms | 256 KB |
31_rand22.txt | WA | 1 ms | 256 KB |
31_rand23.txt | WA | 2 ms | 256 KB |
31_rand24.txt | WA | 1 ms | 256 KB |
41_rand00.txt | WA | 2 ms | 384 KB |
41_rand01.txt | AC | 1 ms | 256 KB |
41_rand02.txt | WA | 4 ms | 512 KB |
41_rand03.txt | WA | 6 ms | 512 KB |
41_rand04.txt | WA | 7 ms | 640 KB |
41_rand05.txt | WA | 3 ms | 512 KB |
41_rand06.txt | WA | 3 ms | 512 KB |
41_rand07.txt | WA | 11 ms | 896 KB |
41_rand08.txt | WA | 1 ms | 256 KB |
41_rand09.txt | WA | 3 ms | 512 KB |
41_rand10.txt | WA | 1 ms | 256 KB |
41_rand11.txt | WA | 7 ms | 640 KB |
41_rand12.txt | WA | 11 ms | 896 KB |
41_rand13.txt | WA | 2 ms | 384 KB |
41_rand14.txt | WA | 4 ms | 512 KB |
41_rand15.txt | WA | 1 ms | 256 KB |
41_rand16.txt | WA | 1 ms | 256 KB |
41_rand17.txt | WA | 6 ms | 512 KB |
41_rand18.txt | WA | 19 ms | 1152 KB |
41_rand19.txt | WA | 17 ms | 1152 KB |
41_rand20.txt | WA | 4 ms | 512 KB |
41_rand21.txt | WA | 1 ms | 256 KB |
41_rand22.txt | WA | 3 ms | 512 KB |
41_rand23.txt | WA | 12 ms | 1024 KB |
41_rand24.txt | WA | 8 ms | 896 KB |