oj.uz

Submission #1043210

# Submission time Handle Problem Language Result Execution time Memory
1043210 2024-08-04T04:51:38 Z model_code Bikeparking (EGOI24_bikeparking) C++17
40 / 100
 509 ms 1048576 KB 
//@EXPECED_GRADES@ AC TLE TLE AC TLE
#include <bits/stdc++.h>
using namespace std;

#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define debug(...) //ignore
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef long double ld;


#include <bits/extc++.h>

const ll INF = numeric_limits<ll>::max() / 4;
typedef vector<ll> VL;

struct MCMF {
  int N;
  vector<vi> ed, red;
  vector<VL> cap, flow, cost;
  vi seen;
  VL dist, pi;
  vector<pii> par;

  MCMF(int N) :
    N(N), ed(N), red(N), cap(N, VL(N)), flow(cap), cost(cap),
    seen(N), dist(N), pi(N), par(N) {}

  void addEdge(int from, int to, ll cap, ll cost) {
    this->cap[from][to] = cap;
    this->cost[from][to] = cost;
    ed[from].push_back(to);
    red[to].push_back(from);
  }

  void path(int s) {
    fill(all(seen), 0);
    fill(all(dist), INF);
    dist[s] = 0; ll di;

    __gnu_pbds::priority_queue<pair<ll, int>> q;
    vector<decltype(q)::point_iterator> its(N);
    q.push({0, s});

    auto relax = [&](int i, ll cap, ll cost, int dir) {
      ll val = di - pi[i] + cost;
      if (cap && val < dist[i]) {
        dist[i] = val;
        par[i] = {s, dir};
        if (its[i] == q.end()) its[i] = q.push({-dist[i], i});
        else q.modify(its[i], {-dist[i], i});
      }
    };

    while (!q.empty()) {
      s = q.top().second; q.pop();
      seen[s] = 1; di = dist[s] + pi[s];
      for (int i : ed[s]) if (!seen[i])
        relax(i, cap[s][i] - flow[s][i], cost[s][i], 1);
      for (int i : red[s]) if (!seen[i])
        relax(i, flow[i][s], -cost[i][s], 0);
    }
    rep(i,0,N) pi[i] = min(pi[i] + dist[i], INF);
  }

  pair<ll, ll> maxflow(int s, int t) {
    ll totflow = 0, totcost = 0;
    while (path(s), seen[t]) {
      ll fl = INF;
      for (int p,r,x = t; tie(p,r) = par[x], x != s; x = p)
        fl = min(fl, r ? cap[p][x] - flow[p][x] : flow[x][p]);
      totflow += fl;
      for (int p,r,x = t; tie(p,r) = par[x], x != s; x = p)
        if (r) flow[p][x] += fl;
        else flow[x][p] -= fl;
    }
    rep(i,0,N) rep(j,0,N) totcost += cost[i][j] * flow[i][j];
    return {totflow, totcost};
  }

  // If some costs can be negative, call this before maxflow:
  void setpi(int s) { // (otherwise, leave this out)
    fill(all(pi), INF); pi[s] = 0;
    int it = N, ch = 1; ll v;
    while (ch-- && it--)
      rep(i,0,N) if (pi[i] != INF)
        for (int to : ed[i]) if (cap[i][to])
          if ((v = pi[i] + cost[i][to]) < pi[to])
            pi[to] = v, ch = 1;
    assert(it >= 0); // negative cost cycle
  }
};

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  int n;
  cin>>n;
  vi x(n), y(n);
  rep(i,0,n) cin>>x[i];
  rep(i,0,n) cin>>y[i];
  int source = 2*n, sink = 2*n+1;
  MCMF mcmf(2*n+2);

  rep(i,0,n) {
    mcmf.addEdge(source, i, y[i], 0);
    mcmf.addEdge(n+i, sink, x[i], 0);
    rep(j,0,n) {
      mcmf.addEdge(i, n+j, 1e9, j < i ? -1 : j == i ? 0 : 1);
    }
  }

  mcmf.setpi(source);
  auto [flow, cost] = mcmf.maxflow(source, sink);
  assert(flow == accumulate(all(y),0));
  cout << -cost << endl;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 356 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #2
0.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 4 ms 1368 KB Output is correct
5 Runtime error 509 ms 1048576 KB Execution killed with signal 9
6 Halted 0 ms 0 KB -

Subtask #3
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Runtime error 428 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 356 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 1 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 1 ms 348 KB Output is correct
26 Correct 0 ms 460 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 0 ms 356 KB Output is correct
29 Correct 1 ms 356 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 460 KB Output is correct
32 Correct 0 ms 460 KB Output is correct
33 Correct 0 ms 352 KB Output is correct
34 Correct 0 ms 352 KB Output is correct
35 Correct 0 ms 352 KB Output is correct
36 Correct 0 ms 356 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Correct 0 ms 348 KB Output is correct
39 Correct 0 ms 352 KB Output is correct
40 Correct 0 ms 348 KB Output is correct
41 Correct 0 ms 460 KB Output is correct
42 Correct 0 ms 360 KB Output is correct
43 Correct 5 ms 1372 KB Output is correct
44 Correct 7 ms 1576 KB Output is correct
45 Correct 1 ms 348 KB Output is correct
46 Correct 0 ms 456 KB Output is correct
47 Correct 0 ms 348 KB Output is correct
48 Correct 0 ms 348 KB Output is correct
49 Correct 0 ms 348 KB Output is correct
50 Correct 7 ms 1576 KB Output is correct
51 Correct 6 ms 1576 KB Output is correct
52 Correct 11 ms 1372 KB Output is correct
53 Correct 6 ms 1372 KB Output is correct
54 Correct 6 ms 1556 KB Output is correct
55 Correct 6 ms 1484 KB Output is correct
56 Correct 8 ms 1372 KB Output is correct
57 Correct 4 ms 1376 KB Output is correct
58 Correct 5 ms 1372 KB Output is correct
59 Correct 6 ms 1372 KB Output is correct
60 Correct 4 ms 1376 KB Output is correct
61 Correct 4 ms 1372 KB Output is correct
62 Correct 10 ms 1584 KB Output is correct
63 Correct 8 ms 1568 KB Output is correct
64 Correct 7 ms 1372 KB Output is correct
65 Correct 7 ms 1484 KB Output is correct
66 Correct 10 ms 1588 KB Output is correct
67 Correct 1 ms 1372 KB Output is correct
68 Correct 1 ms 1432 KB Output is correct
69 Correct 1 ms 1372 KB Output is correct
70 Correct 1 ms 1412 KB Output is correct
71 Correct 0 ms 348 KB Output is correct
72 Correct 0 ms 348 KB Output is correct
73 Correct 0 ms 348 KB Output is correct
74 Correct 1 ms 348 KB Output is correct
75 Correct 0 ms 348 KB Output is correct
76 Correct 0 ms 348 KB Output is correct
77 Correct 0 ms 348 KB Output is correct
78 Correct 0 ms 352 KB Output is correct
79 Correct 0 ms 348 KB Output is correct
80 Correct 2 ms 1372 KB Output is correct
81 Correct 4 ms 1584 KB Output is correct
82 Correct 4 ms 1372 KB Output is correct
83 Correct 3 ms 1376 KB Output is correct
84 Correct 4 ms 1480 KB Output is correct
85 Correct 4 ms 1372 KB Output is correct
86 Correct 3 ms 1372 KB Output is correct
87 Correct 4 ms 1372 KB Output is correct
88 Correct 0 ms 348 KB Output is correct
89 Correct 1 ms 352 KB Output is correct
90 Correct 0 ms 348 KB Output is correct
91 Correct 0 ms 352 KB Output is correct

Subtask #5
0.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 356 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 1 ms 348 KB Output is correct
24 Correct 0 ms 348 KB Output is correct
25 Correct 4 ms 1368 KB Output is correct
26 Runtime error 509 ms 1048576 KB Execution killed with signal 9
27 Halted 0 ms 0 KB -