Download Speed

#include <bits/stdc++.h>

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

static bool bfs(const int current, const int goal, const std::vector<std::vector<Edge>>& graph, std::vector<int>& parentVertex, std::vector<int>& parentEdge) {
    const size_t n = graph.size();
    std::vector visited(n, false);
    parentVertex[current] = current;

    std::queue<int> q;
    q.push(current);
    visited[current] = true;

    while (!q.empty()) {
        const int v = q.front(); q.pop();

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

            if (e.cap > 0 && !visited[e.to]) {
                parentVertex[e.to] = v;
                parentEdge[e.to] = i;
                visited[e.to] = true;

                if (e.to == goal) {
                    return true;
                }

                q.push(e.to);
            }
        }
    }

    return false;
}

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

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

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

    long long maxFlow = 0;

    std::vector<int> parentVertex(n + 1), parentEdge(n + 1);
    while (bfs(1, n, graph, parentVertex, parentEdge)) {
        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;
    }

    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

double free or corruption (!prev)

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