# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
296416 |
2020-09-10T14:28:21 Z |
morato |
Traffic (IOI10_traffic) |
C++17 |
|
17 ms |
23900 KB |
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 5;
vector<int> adj[maxn];
int64_t p[maxn], h[maxn], sub[maxn], tot;
int64_t dfs(int v, int _p = -1) {
sub[v] = p[v];
for (int u : adj[v]) if (u != _p) {
int64_t wgt = dfs(u, v);
sub[v] += wgt;
h[v] = max(h[v], wgt);
}
return sub[v];
}
int LocateCentre(int N, int P[], int S[], int D[]) {
for (int i = 0; i < N; i++) {
p[i] = P[i];
}
for (int i = 0; i < N; i++) {
adj[S[i]].push_back(D[i]);
adj[D[i]].push_back(S[i]);
}
dfs(0);
int ans = 0;
int64_t heavy = sub[0] - p[0];
for (int i = 1; i < N; i++) {
h[i] = max(h[i], sub[0] - sub[i]);
if (h[i] < heavy) {
heavy = h[i];
ans = i;
}
}
return ans;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23900 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |