# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
333220 |
2020-12-05T00:44:19 Z |
daveeed |
Traffic (IOI10_traffic) |
C++17 |
|
14 ms |
23808 KB |
#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 1000005;
int N;
long long sz[MAXN], ans[MAXN], tot;
vector<int> adj[MAXN];
void dfs(int i, int par){
for(int v: adj[i]){
if(v == par)
continue;
dfs(v, i);
ans[i] = max(ans[i], sz[v]);
sz[i] += sz[v];
}
ans[i] = max(ans[i], tot - sz[i]);
}
int LocateCentre(int n, int P[], int S[], int D[]){
N = n;
for(int i = 0; i < N; i++){
sz[i] = P[i];
tot += sz[i];
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0, -1);
int mxi = 0;
for(int i = 1; i < N; i++){
if(ans[i] < ans[mxi])
mxi = i;
}
return mxi;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
14 ms |
23808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
14 ms |
23808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
14 ms |
23808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
14 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
14 ms |
23808 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |