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
AC × 25
AC × 33
WA × 17
AC × 35
WA × 40
AC × 36
WA × 64
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