| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 427331 | cpp219 | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#pragma GCC optimization "O2"
#pragma GCC optimization "unroll-loop"
#pragma GCC target ("avx2")
#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
const ll N = 1e12 + 9;
const ll inf = 1e9 + 7;
const ll Log2 = 20;
typedef pair<ll,ll> LL;
vector<ll> g[N];
ll n,a[N],mn = inf,chosen,child[N],InitChild[N],sum;
set<LL> s[N];
void DFSinit(ll u,ll p){
child[u] = a[u];
for (auto i : g[u]){
if (i == p) continue;
DFSinit(i,u); child[u] += child[i];
s[u].insert({child[i],i});
}
InitChild[u] = child[u];
}
void DFS(ll u,ll p){
if (!s[u].empty()){
LL now = *s[u].rbegin(),rm = {sum - child[u],-1};
now = max(now,rm);
if (now.fs < mn) mn = now.fs,chosen = u;
}
for (auto i : g[u]){
if (i == p) continue;
s[u].erase({child[i],i}); s[i].insert({sum - child[i],u});
//cout<<child[i]<<" "<<i; exit(0);
child[u] = sum - child[i]; child[i] = sum;
DFS(i,u);
}
if (p >= 0){
child[u] = InitChild[u];
s[p].insert({child[u],u}); s[u].erase({child[p],p});
child[p] = InitChild[p];
}
}
ll LocateCentre(ll sz,ll P[],ll X[],ll Y[]){
n = sz;
for (ll i = 0;i < n;i++) a[i] = P[i],sum += a[i];
for (ll i = 0;i < n - 1;i++){
g[X[i]].push_back(Y[i]); g[Y[i]].push_back(X[i]);
}
DFSinit(0,-1); DFS(0,-1);
return chosen;
}