Submission #686570

#	Time	Username	Problem	Language	Result	Execution time	Memory
686570		saayan007	Traffic (IOI10_traffic)	C++17	100 / 100	1268 ms	202180 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pi = pair<int, int>;
using pl = pair<long long, long long>;
using vi = vector<int>;
using vl = vector<long long>;
using vpi = vector<pair<int, int>>;
using vpl = vector<pair<long long, long long>>;

#define fur(i, a, b) for(ll i = a; i <= (ll)b; ++i)
#define ruf(i, a, b) for(ll i = a; i >= (ll)b; --i)
#define fr first 
#define sc second
#define mp make_pair
#define pb emplace_back
#define nl "\n"
#define all(x) (x).begin(),(x).end()
#define rall(x) (x).rbegin(),(x).rend()

const ll inf = 2e9L + 5;
void st_evth(ll cur, ll src, vl &cnt, vl &cong, int pp[], vl adj[]) {
    cnt[cur] = pp[cur];
    cong[cur] = 0;
    for(auto u : adj[cur]) {
        if(u != src) {
            st_evth(u, cur, cnt, cong, pp, adj);
            cnt[cur] += cnt[u];
            cong[cur] = max(cong[cur], cnt[u]);
        }
    }
}

void dfs(ll cur, ll src, vl &cnt, vl &cong, int pp[], vl adj[], vl &ans) {
    ll opt = 0;
    for(auto u : adj[cur]) {
        if(u != src) {
            opt = max(opt, cnt[u]);
        } else {
            opt = max(opt, cnt[0] - cnt[cur]);
        }
    }
    ans[cur] = opt; 

    for(auto u : adj[cur]) {
        if(u != src) {
            dfs(u, cur, cnt, cong, pp, adj, ans);
        }
    }
}

int LocateCentre(int n, int pp[], int S[], int D[]) {
    vl adj[n];
    fur(i, 0, n - 2) {
        adj[S[i]].pb(D[i]);
        adj[D[i]].pb(S[i]);
    }


    vl cnt(n);
    vl cong(n);

    st_evth(0, -1, cnt, cong, pp, adj);
    
    vl ans(n);
    dfs(0, -1, cnt, cong, pp, adj, ans);

    pl best = {inf, -1};
    fur(i, 0, n - 1) {
        best = min(best, {ans[i], i});
    }

    return best.sc;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25