Download Speed

#include <bits/stdc++.h>

struct Edge {
    int to;
    int rev;
    long long cap;
};

static bool dfs(const int current, const int goal, const long long threshold, const std::vector<std::vector<Edge>>& graph, std::vector<bool>& visited, std::vector<int>& parentVertex, std::vector<int>& parentEdge) {
    if (current == goal) return true;

    visited[current] = true;

    for (int i = 0; i < static_cast<int>(graph[current].size()); i++) {
        const Edge& e = graph[current][i];

        if (e.cap >= threshold && !visited[e.to]) {
            parentVertex[e.to] = current;
            parentEdge[e.to] = i;

            if (dfs(e.to, goal, threshold, graph, visited, parentVertex, parentEdge)) {
                return true;
            }
        }
    }

    return false;
}

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

    int n, m;
    std::cin >> n >> m;

    long long threshold = 0;
    std::vector<std::vector<Edge>> graph(n + 1);
    while (m--) {
        int a, b;
        long long c;
        std::cin >> a >> b >> c;

        int forwardIndex = static_cast<int>(graph[a].size());
        int reverseIndex = static_cast<int>(graph[b].size());

        if (a == b) reverseIndex++;

        graph[a].emplace_back(b, reverseIndex, c);
        graph[b].emplace_back(a, forwardIndex, 0);

        threshold += c;
    }

    long long maxFlow = 0;

    while (threshold > 0) {
        while (true) {
            std::vector visited(n + 1, false);
            std::vector<int> parentVertex(n + 1, -1), parentEdge(n + 1, -1);

            if (!dfs(1, n, threshold, graph, visited, parentVertex, parentEdge)) {
                break;
            }

            long long pushed = std::numeric_limits<long long>::max();
            for (int v = n; v != 1; v = parentVertex[v]) {
                pushed = std::min(pushed, graph[parentVertex[v]][parentEdge[v]].cap);
            }

            for (int v = n; v != 1; v = parentVertex[v]) {
                const int p = parentVertex[v];
                const int edge = parentEdge[v];
                const int rev_edge = graph[p][edge].rev;

                graph[p][edge].cap -= pushed;
                graph[p][rev_edge].cap += pushed;
            }

            maxFlow += pushed;
        }

        threshold /= 2;
    }

    std::cout << maxFlow << std::endl;
    return 0;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: TIME LIMIT EXCEEDED

Test 6

Verdict: RUNTIME ERROR

corrupted size vs. prev_size

Test 7

Verdict: ACCEPTED

Test 8

Verdict: TIME LIMIT EXCEEDED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED