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<pair<int, int>>>& adj, vector<vector<pair<int, int>>>& rAdj, int threshold, int index, int destination, int minVal)
{
    if (index == destination)
        return minVal;

    for (auto& neighbour : adj[index])
    {
        if (neighbour.second >= threshold)
        {
            int val = dfs(adj, rAdj, threshold, neighbour.first, destination, min(neighbour.second, minVal));
            if (val != 0)
            {
                //cout << neighbour.first << " ";
                //rAdj[neighbour]
                neighbour.second -= val;
                return val;
            }
        }
    }

    return 0;
}

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

    vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
    vector<vector<pair<int, int>>> rAdj(n, vector<pair<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});
        rAdj[b].push_back({a, c});
        initialThreshold += c;
    }
    initialThreshold /= 2;
    
    //cout << "Staring path find" << endl;

    int result = 0;
    bool run = true;
    while (run)
    {
        int i;
        for (i = initialThreshold; i > 0; i >>= 1)
        {
            int val = dfs(adj, rAdj, i, 0, n - 1, INT_MAX);
            if (val != 0)
            {
                result += val;
                //cout << endl;
                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: WRONG ANSWER

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: WRONG ANSWER

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: WRONG ANSWER