Download Speed

input/code.cpp: In function 'll maxflow(ll, ll)':
input/code.cpp:93:21: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   93 |     while (new_flow = bfs(s, t, parent)) {
      |            ~~~~~~~~~^~~~~~~~~~~~~~~~~~~

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;

ll n, maxLog;
vector<vector<ll>> up;
vector<ll> depth;
ll m;
vector<vector<ll>> capacity;
vector<vector<ll>> adj;

void preprocess(vector<ll>& parent) {
    depth[1] = 0;
    for (ll i = 2; i <= n; i++) {
        depth[i] = depth[parent[i]] + 1;
    }
    
    for (ll i = 1; i <= n; i++) {
        up[i][0] = parent[i];
    }
    
    for (ll k = 1; k < maxLog; k++) {
        for (ll node = 1; node <= n; node++) {
            up[node][k] = up[up[node][k-1]][k-1];
        }
    }
}

ll ancestor(ll x, ll k) {
    for (ll i = 0; i < maxLog; i++) {
        if (k & (1 << i)) {
            x = up[x][i];
            if (x == 0) return 0;
        }
    }
    return x;
}

ll lca(ll a, ll b) {
    if (depth[a] < depth[b]) swap(a, b);
    
    a = ancestor(a, depth[a] - depth[b]);
    
    if (a == b) return a;
    
    for (ll k = maxLog - 1; k >= 0; k--) {
        if (up[a][k] != up[b][k]) {
            a = up[a][k];
            b = up[b][k];
        }
    }
    
    return up[a][0];
}




ll bfs(ll s, ll t, vector<ll>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<ll, ll>> q;
    q.push({s, LLONG_MAX});
    
    while (!q.empty()) {
        ll cur = q.front().first;
        ll flow = q.front().second;
        q.pop();
        
        for (ll next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                ll new_flow = min(flow, capacity[cur][next]);
                if (next == t) return new_flow;
                q.push({next, new_flow});
            }
        }
    }
    
    return 0;
}

ll maxflow(ll s, ll t) {
    ll flow = 0;
    vector<ll> parent(n + 1);
    ll new_flow;
    
    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        ll cur = t;
        while (cur != s) {
            ll prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }
    
    return flow;
}

int main() {
    /*ll q;
    cin >> n >> q;
    maxLog = ceil(log2(n)) + 1;
    up.assign(n + 1, vector<ll>(maxLog, 0));
    depth.assign(n + 1, 0);
    vector<ll> parent(n + 1, 0);

    for(ll i = 2; i <= n; i++){
       cin >> parent[i];
    }

    preprocess(parent);
    
    for(ll i = 0; i < q; i++){
        ll a, b;
        cin >> a >> b;
        cout << lca(a, b) << "\n";
    }

    return 0;*/

     cin >> n >> m;
    capacity.assign(n + 1, vector<ll>(n + 1, 0));
    adj.assign(n + 1, vector<ll>());
    
    for (ll i = 0; i < m; i++) {
        ll a, b, c;
        cin >> a >> b >> c;
        capacity[a][b] += c;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    cout << maxflow(1, n) << "\n";
    
    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: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED