QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#431817#3179. Cordon BleujuancsWA 0ms3776kbC++203.0kb2024-06-06 09:21:012024-06-06 09:21:01

Judging History

This is the latest submission verdict.

  • [2024-06-06 09:21:01]
  • Judged
  • Verdict: WA
  • Time: 0ms
  • Memory: 3776kb
  • [2024-06-06 09:21:01]
  • Submitted

answer

#include <bits/stdc++.h>
#define el '\n'
#define forn(i, n) for(int i = 0; i < (int)n; ++i)
#define for1(i, n) for(int i = 1; i <= (int)n; ++i)
#define fore(i, l, r)for(int i = l; i <= (int)r; ++i)
#define fored(i, l, r)for(int i = r; i >= (int)l; --i)
#define all(a) a.begin(), a.end()
#define d(x) cerr<<#x<<" "<<x<<el
#define sz(x) x.size()
#define pb push_back
#define fi first
#define se second

using namespace std;
typedef long long ll;
typedef double ld;
typedef vector<ll> vll;
typedef vector<int> vi;
typedef array<int, 4> a4;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;

const ll inf = 1e18;
struct edge{
  int to, rev; ll cap, cos, f{0};
  edge(int to, int rev, ll cap, ll cos):to(to), rev(rev), cap(cap), cos(cos){}
};
struct MCMF{
  int n, s, t; 
  vector<vector<edge>> g;
  vi p;  vll dis;
  MCMF(int n): n(n), g(n){}
  void addEdge(int s, int t, ll cap, ll cos){
    g[s].pb(edge(t, sz(g[t]), cap, cos));
    g[t].pb(edge(s, sz(g[s])-1, 0, -cos));
  }
  void spfa(int v0){
    dis.assign(n, inf); dis[v0] = 0;
    p.assign(n, -1);
    vector<bool> inq(n);
    queue<int> q({v0});
    while(sz(q)){
      int u = q.front(); q.pop();
      inq[u] = 0;
      for(auto&[v, rev, cap, cos, f] : g[u]){
        if(cap - f > 0 && dis[v] > dis[u] + cos){
          dis[v] = dis[u] + cos, p[v] = rev;
          if(!inq[v]) inq[v] = 1, q.push(v);
        }
      }
    }
  }
  ll min_cos_flow(ll K){
    ll flow = 0, cost = 0;
    while(flow < K){
      spfa(s);
      if(dis[t] == inf) break;
      ll f = K - flow;    
      int cur = t; // Find flow
      while(cur != s){  
        int u = g[cur][p[cur]].to, rev = g[cur][p[cur]].rev;
        f = min(f, g[u][rev].cap - g[u][rev].f);
        cur = u;
      }
      flow += f,  cost += f * dis[t],  cur = t;     // Apply flow
      while(cur != s){
        int u = g[cur][p[cur]].to, rev = g[cur][p[cur]].rev;
        g[u][rev].f += f,  g[cur][p[cur]].f -= f;
        cur = u;
      }
    }
    if(flow < K) assert(0);
    return cost;
  }
};

struct pt{
    int x, y;
    pt(){}
    pt(int x, int y): x(x), y(y){}
    ll dst(pt p){return abs(x - p.x) + abs(y - p.y); }
};

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.precision(21);
    int n, m;
    cin >> n >> m;
    vector<pt> wn(n), crs(m);
    forn(j, n)cin >> wn[j].x >> wn[j].y;
    forn(i, m)cin >> crs[i].x >> crs[i].y;
    pt rst = pt();
    cin >> rst.x >> rst.y;
    int N = n + m + 3;
    MCMF flw = MCMF(N);
    flw.s = 0;
    flw.t = 1;
    forn(i, m){
        flw.addEdge(0, i + 3, 1, 0);
    }
    flw.addEdge(0, 2, n - 1, 0);

    forn(i, m){
        forn(j, n){
            flw.addEdge(i + 3, j + m + 3, 1, crs[i].dst(wn[j]));
        }
    }
    forn(j, n){
        flw.addEdge(2, j + m + 3, 1, rst.dst(wn[j]));
    }

    forn(j, n){
        flw.addEdge(j + m + 3, 1, 1, rst.dst(wn[j]));
    }
    ll ans = flw.min_cos_flow(m);
    cout << ans << el;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3740kb

input:

1 1
-324 -832
-324 -832
-324 -832

output:

0

result:

ok single line: '0'

Test #2:

score: 0
Accepted
time: 0ms
memory: 3456kb

input:

2 2
1 0
0 -1
-1 1
2 -1
0 0

output:

5

result:

ok single line: '5'

Test #3:

score: 0
Accepted
time: 0ms
memory: 3776kb

input:

1 1
597 546
-353 -842
597 546

output:

2338

result:

ok single line: '2338'

Test #4:

score: 0
Accepted
time: 0ms
memory: 3744kb

input:

1 1
-224 757
122 562
122 562

output:

1082

result:

ok single line: '1082'

Test #5:

score: -100
Wrong Answer
time: 0ms
memory: 3504kb

input:

3 1
-941 122
-941 122
-941 122
-763 292
976 473

output:

2616

result:

wrong answer 1st lines differ - expected: '11688', found: '2616'