| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 638419 | ojoConmigo | Traffic (IOI10_traffic) | C++17 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include "traffic.h"
//#include <bits/stdc++.h>
//using namespace std;
vector<vector<int>> g;
vector<long long> fir,sec,ans,subarbol;
void dfs1(int nodo, int p, int pp[]){
for(int v : g[nodo]){
if(v == p)continue;
dfs1(v,nodo,pp);
subarbol[nodo] += subarbol[v] + pp[v];
if(subarbol[v] + pp[v] > fir[nodo]){
sec[nodo] = fir[nodo];
fir[nodo] = subarbol[v] + pp[v];
}else if(subarbol[v] + pp[v] > sec[nodo]){
sec[nodo] = subarbol[v] + pp[v];
}
}
//cout << nodo << " " << fir[nodo] << " " << sec[nodo] << endl;
}
void dfs2(int nodo, int p, long long cont, int pp[]){
ans[nodo] = max(cont,fir[nodo]);
for(int v : g[nodo]){
if(v == p)continue;
if(subarbol[v] + pp[v] == fir[nodo]) dfs2(v,nodo,(cont > sec[nodo] ? cont + subarbol[nodo] - subarbol[v] : sec[nodo] + pp[nodo]),pp);
else dfs2(v,nodo,cont + subarbol[nodo] - subarbol[v], pp);
}
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
g.resize(N);
for(int i=0; i<N-1; i++){
int x,y;
x = S[i]; y = D[i];
//cout << x << " " << y << endl;
g[x].push_back(y);
g[y].push_back(x);
}
fir.assign(N,0);
sec.assign(N,0);
subarbol.assign(N,0);
ans.resize(N);
dfs1(0,-1,pp);
dfs2(0,-1,0,pp);
int arena = 0;
long long congestion = 2e9 + 1;
for(int i=0; i<N; i++){
//cout << i << " " << ans[i] << " " << congestion << endl;
if(ans[i] < congestion){
congestion = ans[i];
arena = i;
}
}
//cout << arena << endl;
return arena;
/*
long long pre[N];
pre[0] = pp[0];
for(int i=1; i<N; i++){
pre[i] = pre[i-1] + pp[i];
}
int sol = 0;
long long congestion = pre[N-1] - pre[0];
for(int i=1; i<N; i++){
long long mayor = (pre[i-1] > pre[N-1] - pre[i] ? pre[i-1] : pre[N-1] - pre[i]);
//cout << mayor << endl;
if(mayor < congestion){
congestion = mayor;
sol = i;
}
}
return sol;
*/
}
/*
int main(){
int n;
cin >> n;
int pp[n],s[n-1],d[n-1];
for(int i=0; i<n; i++){
cin >> pp[i];
}
for(int i=0; i<n-1; i++){
cin >> s[i] >> d[i];
}
cout << LocateCentre(n,pp,s,d) << endl;
}
*/