Download Speed

#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;
}

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

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

    int n, m;
    cin >> n >> m;
    graph = vector<vector<Edge> >(n + 1);
    ll maxW = 0;
    for (int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        maxW = max(maxW, w);
        Edge a = {v, w, (int) graph[v].size(), false};
        Edge b = {u, 0, (int) graph[u].size(), true};
        graph[u].push_back(a);
        graph[v].push_back(b);
    }

    // source and sink
    int s = 1;
    int t = n;

    ll delta = 1;
    while (delta <= maxW) delta <<= 1;
    delta >>= 1;

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

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

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