Submission #634944

#	Time	Username	Problem	Language	Result	Execution time	Memory
634944		slime	Coin Collecting (JOI19_ho_t4)	C++14	8 / 100	1089 ms	38408 KiB

joi2019_ho_t4

#include "bits/stdc++.h"
#define int long long
using namespace std;
 
struct coin {
    int ox, oy; // original x, y
    int nx, ny; // new x, y
    int cost = 0;
};

struct flow_network {
  struct edge {
    int to, cost, flow, revid; // reverse edge id in adjacency list
  };
  vector<vector<edge> > adj, adj2;
  bool computed = 0;
  int mc, mf;
  int n, s, t;
  public:
  void init(int n_, int s_, int t_) {
    n = n_;
    s = s_;
    t = t_;
    adj.resize(n + 10);
  }
  void addedge(int u, int v, int cost, int flow) {
    int au = adj[u].size();
    int av = adj[v].size();
    adj[u].push_back({v, cost, flow, av});
    adj[v].push_back({u, -cost, 0, au});
  }
  void eval() {
    computed = 1;
    mc = mf = 0;
    int h[n+1];
    for(int i=1; i<=n; i++) h[i] = 0;
    while(1) {
      int dist[n+1];
      pair<int, int> pre[n+1];
      bool vis[n+1];
      priority_queue<pair<int, int>, vector<pair<int, int> > ,greater<pair<int, int> > > pq;
      for(int i=1; i<=n; i++) {
        dist[i] = 1e15;
        vis[i] = 0;
      }
      dist[s] = 0;
      pq.push({0, s});
      while(pq.size()) {
        pair<int, int> t = pq.top(); pq.pop();
        if(!vis[t.second]) {
          vis[t.second] = 1;
          int idx = 0;
          for(edge x: adj[t.second]) {
            if(!vis[x.to] && x.flow > 0 && dist[x.to] > dist[t.second] + x.cost + h[t.second] - h[x.to]) {
              dist[x.to] = dist[t.second] + x.cost + h[t.second] - h[x.to];
              pre[x.to] = {t.second, idx};
              pq.push({dist[x.to], x.to});
            }
            idx++;
          }
        }
      }
      if(dist[t] == 1e15) break;

      int e = 1e15; // amount of flow
      int cur = t;
      while(cur != s) {
        int pv = pre[cur].first;
        int bc = pre[cur].second; // pv -> cur
        int lo = adj[pv][bc].revid; // cur -> pv
        e = min(e, adj[pv][bc].flow);
        cur = pv;
      }
      cur = t;
      while(cur != s) {
        int pv = pre[cur].first;
        int bc = pre[cur].second; // pv -> cur
        int lo = adj[pv][bc].revid; // cur -> pv
        adj[pv][bc].flow -= e;
        adj[cur][lo].flow += e;
        cur = pv;
      }
      mc += (dist[t] - (h[s] - h[t])) * e;
      mf += e;
     // cout << e << " " << (dist[t] - (h[s] - h[t])) << "\n";
      for(int i=1; i<=n; i++) h[i] += dist[i];
    }
  }
  int mincost() {
    if(!computed) eval();
    return mc;
  }
  int maxflow() {
    if(!computed) eval();
    return mf;
  }
};

void solve(int tc) {
    int n;
    cin >> n;
    coin c[2*n + 1];
    for(int i=1; i<=2*n; i++) {
        cin >> c[i].ox >> c[i].oy;
        if(c[i].ox > n) {
            if(c[i].oy >= 2) { // Choose (n, 2)
                c[i].nx = n;
                c[i].ny = 2;
            }
            else { // Choose (n, 1)
                c[i].nx = n;
                c[i].ny = 1;
            }
        }
        else if(c[i].ox < 1) {
            if(c[i].oy >= 2) {
                c[i].nx = 1;
                c[i].ny = 2;
            }
            else {
                c[i].nx = 1;
                c[i].ny = 1;
            }
        }
        else { 
            if(c[i].oy >= 2) {
                c[i].nx = c[i].ox;
                c[i].ny = 2;
            }
            else {
                c[i].nx = c[i].ox;
                c[i].ny = 1;
            }
        }
 
        c[i].cost = abs(c[i].ox - c[i].nx) + abs(c[i].oy - c[i].ny);
    }
    int base = 0;
    for(int i=1; i<=2*n; i++) base += c[i].cost;
    int cnt[n+1][3];
    for(int i=1; i<=n; i++) {
        for(int j=1; j<=2; j++) {
            cnt[i][j] = 0;
        }
    }
 
    for(int i=1; i<=2*n; i++) cnt[c[i].nx][c[i].ny]++;

    flow_network fln;
    fln.init(2*n + 2, 2*n + 1, 2*n + 2);

    for(int i=1; i<=2*n; i++) {
        int x = (i>n ? i-n : i);
        int y = (i>n ? 1 : 2);

        if(cnt[x][y] > 1) {
            fln.addedge(2*n + 1, i, 0, cnt[x][y] - 1);
        }
        else if(cnt[x][y] == 0) {
            fln.addedge(i, 2*n + 2, 0, 1);
        }
    }

    for(int i=1; i<=2*n; i++) {
        int xi = (i>n ? i-n : i);
        int yi = (i>n ? 1 : 2);
        for(int j=1; j<=2*n; j++) {
            int xj = (j>n ? j-n : j);
            int yj = (j>n ? 1 : 2);

            if(cnt[xi][yi] > 1 && cnt[xj][yj] == 0) {
                fln.addedge(i, j, abs(xi - xj) + abs(yi - yj), 1);
            }
        }
    }
    
    fln.eval();

    cout << fln.mincost() + base << "\n";
    
 
}
int32_t main() {
    int t = 1;
    // cin >> t;
    for(int i=1; i<=t; i++) solve(i);
}

/*
Test case

4
0 2
3 1
3 1
2 1
4 2
0 3
1 0
1 3

*/

Compilation message (stderr)

joi2019_ho_t4.cpp: In member function 'void flow_network::eval()':
joi2019_ho_t4.cpp:70:13: warning: unused variable 'lo' [-Wunused-variable]
   70 |         int lo = adj[pv][bc].revid; // cur -> pv
      |             ^~

• Subtask 1: 8 / 8
• Subtask 2: 0 / 29
• Subtask 3: 0 / 63