# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
481616 | SlavicG | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define forn(i,n) for(int i=0;i<n;i++)
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(),v.rend()
#define pb push_back
#define sz(a) (int)a.size()
const int N = 1e6 + 10;
vector<int> adj[N];
ll ss[N];
ll mx[N];
void dfs(int u, int par, vector<int>& p){
ss[u] = p[u];
for(int v: adj[u]){
if(v == par)continue;
dfs(v, u, p);
ss[u] += ss[v];
mx[u] = max(mx[u], ss[v]);
}
}
int LocateCentre(int n, vector<int> p, vector<int> s, vector<int> d){
for(int i = 0;i < n - 1;++i){
int u = s[i], v = d[i];
adj[u].pb(v);
adj[v].pb(u);
}
dfs(0, -1, p);
ll ans = mx[0];
int idx = 0;
for(int i = 1;i < n;++i){
if(ans > max(mx[i], ss[0] - ss[i])){
ans = max(mx[i], ss[0] - ss[i]);
idx = i;
}
}
return idx;
}