# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
363041 |
2021-02-05T03:23:54 Z |
nishuz |
Traffic (IOI10_traffic) |
C++14 |
|
16 ms |
23788 KB |
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int MAX = 1e6 + 1;
vector <int> adj[MAX];
ll sum[MAX];
int pars[MAX];
void dfs(int u, int par, int p[])
{
sum[u] = p[u];
pars[u] = par;
for (int v : adj[u])
if (v != par)
dfs(v, u, p);
for (int v : adj[u])
if (v != par)
sum[u] += sum[v];
}
int LocateCentre(int n, int p[], int s[], int d[])
{
for (int i = 0; i < n - 1; ++i)
{
adj[s[i]].emplace_back(d[i]);
adj[d[i]].emplace_back(s[i]);
}
dfs(0, 0, p);
pair <ll, int> ans = make_pair(LLONG_MAX, -1);
for (int u = 0; u < n; ++u)
{
ll m = -1, cur = p[u];
for (int v : adj[u])
{
if (v != pars[u])
{
m = max(m, sum[u]);
cur += p[v];
}
}
if (u) m = max(m, sum[0] - cur);
ans = min(ans, make_pair(m, u));
}
return ans.second;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Incorrect |
16 ms |
23788 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |