# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
296428 |
2020-09-10T14:35:22 Z |
morato |
Traffic (IOI10_traffic) |
C++17 |
|
17 ms |
23936 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];
void dfs(int v, int _p = -1) {
sub[v] = p[v];
for (int u : adj[v]) if (u != _p) {
dfs(u, v);
sub[v] += sub[u];
h[v] = max(h[v], sub[u]);
}
}
int LocateCentre(int N, int P[], int S[], int D[]) {
for (int i = 0; i < N; i++) {
p[i] = 1ll * 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 = h[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 |
23936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
17 ms |
23936 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |