#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define f first
#define s second
#define vi vector<int>
#define vb vector<bool>
#define vvi vector<vector<int>>
#define vii vector<pair<int, int>>
#define vvb vector<vector<bool>>
#define piii pair<int, pair<int, int>>
#define vvpii vector<vector<pair<int, int>>>
#define inf 987654321
#define pb push_back
#define p push
#define ll long long
#define ull unsigned long long
#define g get
#define dbl double
#define mn 1000005
int N, P[mn];
vi adj[mn];
int fans;
int ans[mn];
int dfs (int loc, int par)
{
int sb = 0, mb = 0;
for (auto i : adj[loc])
if (i != par)
sb += dfs(i, loc), mb = max(mb, dfs(i, loc));
ans[loc] = max(mb, fans - sb - P[loc]);
return sb + P[loc];
}
int LocateCentre(int fN, int fP[mn], int S[mn], int D[mn])
{
N = fN;
for (int i = 0; i < N; i++)
P[i] = fP[i], fans += P[i];
for (int i = 0; i < N - 1; i++)
adj[S[i]].pb({D[i]}), adj[D[i]].pb({S[i]});
dfs(0, -1);
int bc = inf, bl;
for (int i = 0; i < N; i++)
if (bc > ans[i])
bc = ans[i], bl = i;
return bl;
}
/*int main(void)
{
cout << "TR" << endl;
int N, P[mn], S[mn], D[mn];
cin >> N;
for (int i = 0; i < N; i++)
cin >> P[i];
for (int i = 0; i < N - 1; i++)
cin >> S[i];
for (int i = 0; i < N - 1; i++)
cin >> D[i];
cout << LocateCentre(N, P, S, D);
}*/
Compilation message
traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:51:12: warning: 'bl' may be used uninitialized in this function [-Wmaybe-uninitialized]
51 | return bl;
| ^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
18 ms |
23788 KB |
Output is correct |
3 |
Correct |
18 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23788 KB |
Output is correct |
6 |
Correct |
19 ms |
23788 KB |
Output is correct |
7 |
Correct |
17 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23788 KB |
Output is correct |
10 |
Correct |
28 ms |
23788 KB |
Output is correct |
11 |
Correct |
17 ms |
23788 KB |
Output is correct |
12 |
Correct |
17 ms |
23788 KB |
Output is correct |
13 |
Correct |
18 ms |
23788 KB |
Output is correct |
14 |
Correct |
20 ms |
23788 KB |
Output is correct |
15 |
Correct |
16 ms |
23788 KB |
Output is correct |
16 |
Correct |
16 ms |
23916 KB |
Output is correct |
17 |
Correct |
18 ms |
23788 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
16 ms |
23788 KB |
Output is correct |
20 |
Correct |
16 ms |
23788 KB |
Output is correct |
21 |
Execution timed out |
5089 ms |
23788 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
18 ms |
23788 KB |
Output is correct |
3 |
Correct |
18 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23788 KB |
Output is correct |
6 |
Correct |
19 ms |
23788 KB |
Output is correct |
7 |
Correct |
17 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23788 KB |
Output is correct |
10 |
Correct |
28 ms |
23788 KB |
Output is correct |
11 |
Correct |
17 ms |
23788 KB |
Output is correct |
12 |
Correct |
17 ms |
23788 KB |
Output is correct |
13 |
Correct |
18 ms |
23788 KB |
Output is correct |
14 |
Correct |
20 ms |
23788 KB |
Output is correct |
15 |
Correct |
16 ms |
23788 KB |
Output is correct |
16 |
Correct |
16 ms |
23916 KB |
Output is correct |
17 |
Correct |
18 ms |
23788 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
16 ms |
23788 KB |
Output is correct |
20 |
Correct |
16 ms |
23788 KB |
Output is correct |
21 |
Execution timed out |
5089 ms |
23788 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
18 ms |
23788 KB |
Output is correct |
3 |
Correct |
18 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23788 KB |
Output is correct |
6 |
Correct |
19 ms |
23788 KB |
Output is correct |
7 |
Correct |
17 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23788 KB |
Output is correct |
10 |
Correct |
28 ms |
23788 KB |
Output is correct |
11 |
Correct |
17 ms |
23788 KB |
Output is correct |
12 |
Correct |
17 ms |
23788 KB |
Output is correct |
13 |
Correct |
18 ms |
23788 KB |
Output is correct |
14 |
Correct |
20 ms |
23788 KB |
Output is correct |
15 |
Correct |
16 ms |
23788 KB |
Output is correct |
16 |
Correct |
16 ms |
23916 KB |
Output is correct |
17 |
Correct |
18 ms |
23788 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
16 ms |
23788 KB |
Output is correct |
20 |
Correct |
16 ms |
23788 KB |
Output is correct |
21 |
Execution timed out |
5089 ms |
23788 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
23788 KB |
Output is correct |
2 |
Correct |
18 ms |
23788 KB |
Output is correct |
3 |
Correct |
18 ms |
23788 KB |
Output is correct |
4 |
Correct |
16 ms |
23788 KB |
Output is correct |
5 |
Correct |
17 ms |
23788 KB |
Output is correct |
6 |
Correct |
19 ms |
23788 KB |
Output is correct |
7 |
Correct |
17 ms |
23788 KB |
Output is correct |
8 |
Correct |
16 ms |
23788 KB |
Output is correct |
9 |
Correct |
17 ms |
23788 KB |
Output is correct |
10 |
Correct |
28 ms |
23788 KB |
Output is correct |
11 |
Correct |
17 ms |
23788 KB |
Output is correct |
12 |
Correct |
17 ms |
23788 KB |
Output is correct |
13 |
Correct |
18 ms |
23788 KB |
Output is correct |
14 |
Correct |
20 ms |
23788 KB |
Output is correct |
15 |
Correct |
16 ms |
23788 KB |
Output is correct |
16 |
Correct |
16 ms |
23916 KB |
Output is correct |
17 |
Correct |
18 ms |
23788 KB |
Output is correct |
18 |
Correct |
17 ms |
23936 KB |
Output is correct |
19 |
Correct |
16 ms |
23788 KB |
Output is correct |
20 |
Correct |
16 ms |
23788 KB |
Output is correct |
21 |
Execution timed out |
5089 ms |
23788 KB |
Time limit exceeded |
22 |
Halted |
0 ms |
0 KB |
- |