#include <bits/stdc++.h>
//#include "traffic.h"
const int maxn = 1e6+10;
std::vector<int> grafo[maxn];
int c[maxn], mx[maxn], mx2[maxn], id[maxn], id2[maxn], ans=11111111, idans;
void dfs(int u, int p=-1){
for(auto v : grafo[u]){
if(v == p) continue;
dfs(v, u);
if(mx[v] + c[v] > mx[u]){
mx2[u] = mx[u], id2[u] = id[u];
mx[u] = mx[v] + c[v], id[u] = v;
}
}
}
int maxi;
void solve(int u, int last=0, int p=-1){
for(auto v : grafo[u]){
if(v == p) continue;
maxi = last;
if(v == id[u] and maxi < mx2[u]) maxi = mx2[u];
if(v == id2[u] and maxi < mx[u]) maxi = mx[u];
solve(v, maxi + c[u], u);
}
if(ans > last and last > mx[u]){
ans = last;
idans = u;
}
else if(ans > mx[u] and mx[u] > last){
ans = mx[u];
idans = u;
}
}
int LocateCentre(int n, int *p, int *s, int *d){
for(int i=0; i<n; i++){
c[i] = p[i];
if(i+1<n){
grafo[s[i]].push_back(d[i]);
grafo[d[i]].push_back(s[i]);
}
}
dfs(0);
solve(0);
return idans;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Incorrect |
20 ms |
23800 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Incorrect |
20 ms |
23800 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Incorrect |
20 ms |
23800 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
23800 KB |
Output is correct |
2 |
Incorrect |
20 ms |
23800 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |