Airport

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <climits>

typedef long long ll;

using namespace std;

struct Edge {
    int to;
    ll cap;
    int rev; // index of reverse edge in G[to]
    bool is_rev;
};

const ll INF = (1LL << 60);
vector<vector<Edge> > graph;
vector<bool> used;


ll dfs(int v, int t, ll f, ll delta) {
    if (v == t) return f;
    used[v] = true;
    for (auto &e: graph[v]) {
        if (!used[e.to] && e.cap >= delta) {
            ll pushed = dfs(e.to, t, min(f, e.cap), delta);
            if (pushed > 0) {
                e.cap -= pushed;
                graph[e.to][e.rev].cap += pushed;
                return pushed;
            }
        }
    }
    return 0;
}

void mark_reachable(int v, vector<char> &reach) {
    reach[v] = 1;
    for (auto &e: graph[v]) {
        if (e.cap > 0 && !reach[e.to]) {
            mark_reachable(e.to, reach);
        }
    }
}

void add_edge(int u, int v, ll cap) {
    Edge a = {v, cap, (int)graph[v].size(), false};
    Edge b = {u, 0,   (int)graph[u].size(), true};
    graph[u].push_back(a);
    graph[v].push_back(b);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // freopen("input.txt", "r", stdin); // TODO: REMOVE THIS YOU STUPID ****

    int n_orig, m;
    cin >> n_orig >> m;

    int N = 2 * n_orig;
    graph = vector<vector<Edge> >(N);

    vector<ll> r(n_orig + 1);
    ll maxFinite = 0;
    for (int i = 1; i <= n_orig; ++i) {
        cin >> r[i];
        if (r[i] != -1) maxFinite = max(maxFinite, r[i]);
    }

    for (int i = 1; i <= n_orig; ++i) {
        int in = 2 * (i - 1);
        int out = in + 1;
        ll cap = (r[i] == -1 ? INF : r[i]);
        add_edge(in, out, cap);
    }

    for (int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        int a_out = 2 * (a - 1) + 1;
        int b_in  = 2 * (b - 1);
        add_edge(a_out, b_in, INF);
    }

    int s = 1;
    int t = 2 * (n_orig - 1);

    ll delta = 1;
    if (maxFinite == 0) delta = 1;
    else {
        while (delta <= maxFinite) delta <<= 1;
        delta >>= 1;
        if (delta == 0) delta = 1;
    }

    ll maxflow = 0;
    while (delta > 0) {
        while (true) {
            used.assign(N, false);
            ll f = dfs(s, t, INF, delta);
            if (f == 0) break;
            maxflow += f;
        }
        delta >>= 1;
    }

    cout << maxflow << "\n";
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED