Task: | Airport |
Sender: | aalto2024h_003 |
Submission time: | 2024-10-23 16:28:12 +0300 |
Language: | C++ (C++11) |
Status: | READY |
Result: | ACCEPTED |
test | verdict | time | |
---|---|---|---|
#1 | ACCEPTED | 0.00 s | details |
#2 | ACCEPTED | 0.00 s | details |
#3 | ACCEPTED | 0.00 s | details |
#4 | ACCEPTED | 0.00 s | details |
#5 | ACCEPTED | 0.00 s | details |
#6 | ACCEPTED | 0.00 s | details |
#7 | ACCEPTED | 0.00 s | details |
#8 | ACCEPTED | 0.00 s | details |
#9 | ACCEPTED | 0.00 s | details |
#10 | ACCEPTED | 0.00 s | details |
#11 | ACCEPTED | 0.01 s | details |
#12 | ACCEPTED | 0.00 s | details |
#13 | ACCEPTED | 0.00 s | details |
Code
#include <bits/stdc++.h>using namespace std;#define int long long#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()typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;const int INF = 1e18;/*** Author: chilli* Date: 2019-04-26* License: CC0* Source: https://cp-algorithms.com/graph/dinic.html* Description: Flow algorithm with complexity $O(VE\log U)$ where $U = \max |\text{cap}|$.* $O(\min(E^{1/2}, V^{2/3})E)$ if $U = 1$; $O(\sqrt{V}E)$ for bipartite matching.* Status: Tested on SPOJ FASTFLOW and SPOJ MATCHING, stress-tested*/struct Dinic {struct Edge {int to, rev;ll c, oc;ll flow() { return max(oc - c, 0LL); } // if you need flows};vi lvl, ptr, q;vector<vector<Edge>> adj;Dinic(int n) : lvl(n), ptr(n), q(n), adj(n) {}void addEdge(int a, int b, ll c, ll rcap = 0) {adj[a].push_back({b, sz(adj[b]), c, c});adj[b].push_back({a, sz(adj[a]) - 1, rcap, rcap});}ll dfs(int v, int t, ll f) {if (v == t || !f) return f;for (int& i = ptr[v]; i < sz(adj[v]); i++) {Edge& e = adj[v][i];if (lvl[e.to] == lvl[v] + 1)if (ll p = dfs(e.to, t, min(f, e.c))) {e.c -= p, adj[e.to][e.rev].c += p;return p;}}return 0;}ll calc(int s, int t) {ll flow = 0; q[0] = s;rep(L,0,31) do { // 'int L=30' maybe faster for random datalvl = ptr = vi(sz(q));int qi = 0, qe = lvl[s] = 1;while (qi < qe && !lvl[t]) {int v = q[qi++];for (Edge e : adj[v])if (!lvl[e.to] && e.c >> (30 - L))q[qe++] = e.to, lvl[e.to] = lvl[v] + 1;}while (ll p = dfs(s, t, LLONG_MAX)) flow += p;} while (lvl[t]);return flow;}bool leftOfMinCut(int a) { return lvl[a] != 0; }};signed main() {cin.tie(0)->sync_with_stdio(0);cin.exceptions(cin.failbit); // RTE if input wrong datatypeint n, m;cin >> n >> m;vector<vector<int>> adj(2 * n);Dinic dinic(2 * n);auto out = [](int i) { return 2 * i + 1; };auto in = [](int i) { return 2 * i; };vector<int> r(n);for (int i = 0; i < n; i++) {cin >> r[i];dinic.addEdge(in(i), out(i), r[i] == -1 ? INF : r[i]);}for (int i = 0; i < m; i++) {int u, v;cin >> u >> v;u--; v--;adj[out(u)].push_back(in(v));dinic.addEdge(out(u), in(v), INF);}cout << dinic.calc(in(0), out(n - 1)) << '\n';}
Test details
Test 1
Verdict: ACCEPTED
input |
---|
10 20 -1 85 7 19 90 72 11 46 65 -1 6 7 9 7 8 4 ... |
correct output |
---|
7 |
user output |
---|
7 |
Test 2
Verdict: ACCEPTED
input |
---|
10 20 -1 80 77 57 77 95 63 98 30 -1 6 7 8 9 7 8 ... |
correct output |
---|
30 |
user output |
---|
30 |
Test 3
Verdict: ACCEPTED
input |
---|
10 20 -1 63 16 42 62 70 9 94 68 -1 10 9 6 8 10 6 ... |
correct output |
---|
25 |
user output |
---|
25 |
Test 4
Verdict: ACCEPTED
input |
---|
10 20 -1 3 86 -1 32 34 9 50 -1 -1 6 7 7 8 9 2 ... |
correct output |
---|
3 |
user output |
---|
3 |
Test 5
Verdict: ACCEPTED
input |
---|
10 20 -1 43 38 -1 7 54 26 97 76 -1 3 9 9 10 6 7 ... |
correct output |
---|
76 |
user output |
---|
76 |
Test 6
Verdict: ACCEPTED
input |
---|
100 1000 -1 425576195 274150382 1021768... |
correct output |
---|
6091126630 |
user output |
---|
6091126630 |
Test 7
Verdict: ACCEPTED
input |
---|
100 1000 -1 769953265 -1 389517741 2323... |
correct output |
---|
769953265 |
user output |
---|
769953265 |
Test 8
Verdict: ACCEPTED
input |
---|
100 1000 -1 584988267 763129662 6781413... |
correct output |
---|
1699511766 |
user output |
---|
1699511766 |
Test 9
Verdict: ACCEPTED
input |
---|
100 1000 -1 921671366 121044688 2933366... |
correct output |
---|
1805833567 |
user output |
---|
1805833567 |
Test 10
Verdict: ACCEPTED
input |
---|
100 1000 -1 763842763 612011030 4532521... |
correct output |
---|
3342235784 |
user output |
---|
3342235784 |
Test 11
Verdict: ACCEPTED
input |
---|
3 3
-1 1 -1 1 2 2 3 2 2 |
correct output |
---|
1 |
user output |
---|
1 |
Test 12
Verdict: ACCEPTED
input |
---|
3 4
-1 1 -1 1 2 1 2 2 3 ... |
correct output |
---|
1 |
user output |
---|
1 |
Test 13
Verdict: ACCEPTED
input |
---|
7 8 -1 1 1 1 1 1 -1 1 2 1 3 2 4 ... |
correct output |
---|
1 |
user output |
---|
1 |