| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 481619 | SlavicG | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "traffic.h"
#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;
}