Download Speed

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <numeric>
#include <unordered_map>
#include <queue>
#include <climits>
#include <cmath>
 
#define int long long
using namespace std;

int dfs(vector<vector<tuple<int, int, int>>>& adj, vector<bool>& visited, int threshold, int index, int destination, int minVal)
{
    if (index == destination)
        return minVal;

    for (auto& neighbour : adj[index])
    {
        if (!visited[get<0>(neighbour)] && get<1>(neighbour) >= threshold)
        {
            visited[get<0>(neighbour)] = true;
            int val = dfs(adj, visited, threshold, get<0>(neighbour), destination, min(get<1>(neighbour), minVal));
            visited[get<0>(neighbour)] = false;
            if (val != 0)
            {
                //cout << get<0>(neighbour) << " ";
                get<1>(neighbour) -= val;
                get<1>(adj[get<0>(neighbour)][get<2>(neighbour)]) += val;
                return val;
            }
        }
    }

    return 0;
}

void solve()
{
    int n, m;
    cin >> n >> m;

    // Tuple: index of connected node, weight, index of backPath
    vector<vector<tuple<int, int, int>>> adj(n, vector<tuple<int, int, int>>());
    int initialThreshold = 0;
    for (int i = 0; i < m; i++)
    {
        int a, b, c;
        cin >> a >> b >> c;
        a--;b--;

        adj[a].push_back({b, c, adj[b].size()});
        adj[b].push_back({a, 0, adj[a].size()-1});
        initialThreshold += c;
    }
    
    //cout << "Starting path find\n";
    vector<bool> visited(n, false);

    int result = 0;
    bool run = true;
    while (run)
    {
        int i;
        for (i = initialThreshold; i > 0; i >>= 1)
        {
            int val = dfs(adj, visited, i, 0, n - 1, INT_MAX);
            if (val != 0)
            {
                result += val;
                //cout << " TOTAL: " << val << endl;//DEBUG("\n");
                break;
            }
        }
        if (i == 0)
            run = false;
    }
    
    cout << result << endl;
}
 
signed main()
{
    int t = 1;
 
    // cin >> t;
 
    for (int i = 0; i < t; i++)
        solve();
 
    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: TIME LIMIT EXCEEDED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED