# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377739 | 2021-03-14T21:53:56 Z | AlexRex0 | Traffic (IOI10_traffic) | C++14 | 5000 ms | 23916 KB |
#include "traffic.h" #include <stdio.h> #include <bits/stdc++.h> using namespace std; vector<int> g[1000002]; long long int sub[1000002]; bool visitado[1000002]; int v[1000002]; long long int dfs(int nodo, int padre){ sub[nodo]+= v[nodo]; for(int i = 0 ; i < g[nodo].size(); ++i){ if(g[nodo][i] != padre){ sub[nodo]+= dfs(g[nodo][i], nodo); } } return sub[nodo]; } long long int indRes, indMax = -1, Max, aux, Res, ayuda; static int N,P[1000000],S[1000000],D[1000000]; int LocateCentre(int N, int pp[], int S[], int D[]) { for(int i = 0; i < N - 1; ++i){ g[S[i]].push_back(D[i]); g[D[i]].push_back(S[i]); v[i] = pp[i]; } v[N - 1] = pp[N - 1]; dfs(0, -1); Max = -1; for(int i = 0; i < g[0].size(); ++i){ ayuda = sub[g[0][i]]; if(ayuda > Max){ Max = ayuda; } } Res = Max; while(true){ Max = -1; for(int i = 0; i < g[aux].size(); ++i){ ayuda = sub[g[aux][i]]; if(ayuda > Max){ Max = ayuda; indMax = g[aux][i]; } } if(Max < Res){ indRes = aux; Res = Max; } sub[aux]-= sub[indMax]; sub[indMax]+= sub[aux]; if(indRes == indMax){ break; } aux = indMax; } return indRes; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23788 KB | Output is correct |
2 | Correct | 16 ms | 23788 KB | Output is correct |
3 | Correct | 16 ms | 23788 KB | Output is correct |
4 | Correct | 16 ms | 23788 KB | Output is correct |
5 | Correct | 16 ms | 23788 KB | Output is correct |
6 | Correct | 16 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 16 ms | 23788 KB | Output is correct |
9 | Correct | 16 ms | 23788 KB | Output is correct |
10 | Correct | 16 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 | 17 ms | 23788 KB | Output is correct |
14 | Correct | 17 ms | 23892 KB | Output is correct |
15 | Correct | 16 ms | 23788 KB | Output is correct |
16 | Correct | 16 ms | 23788 KB | Output is correct |
17 | Correct | 16 ms | 23788 KB | Output is correct |
18 | Correct | 16 ms | 23788 KB | Output is correct |
19 | Correct | 16 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 17 ms | 23788 KB | Output is correct |
22 | Correct | 17 ms | 23788 KB | Output is correct |
23 | Correct | 16 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 16 ms | 23788 KB | Output is correct |
26 | Correct | 17 ms | 23916 KB | Output is correct |
27 | Correct | 16 ms | 23916 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 17 ms | 23916 KB | Output is correct |
31 | Correct | 17 ms | 23916 KB | Output is correct |
32 | Correct | 17 ms | 23916 KB | Output is correct |
33 | Correct | 17 ms | 23916 KB | Output is correct |
34 | Correct | 16 ms | 23788 KB | Output is correct |
35 | Correct | 17 ms | 23916 KB | Output is correct |
36 | Correct | 17 ms | 23916 KB | Output is correct |
37 | Correct | 17 ms | 23916 KB | Output is correct |
38 | Correct | 17 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 18 ms | 23916 KB | Output is correct |
41 | Correct | 17 ms | 23916 KB | Output is correct |
42 | Correct | 17 ms | 23916 KB | Output is correct |
43 | Execution timed out | 5066 ms | 23788 KB | Time limit exceeded |
44 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23788 KB | Output is correct |
2 | Correct | 16 ms | 23788 KB | Output is correct |
3 | Correct | 16 ms | 23788 KB | Output is correct |
4 | Correct | 16 ms | 23788 KB | Output is correct |
5 | Correct | 16 ms | 23788 KB | Output is correct |
6 | Correct | 16 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 16 ms | 23788 KB | Output is correct |
9 | Correct | 16 ms | 23788 KB | Output is correct |
10 | Correct | 16 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 | 17 ms | 23788 KB | Output is correct |
14 | Correct | 17 ms | 23892 KB | Output is correct |
15 | Correct | 16 ms | 23788 KB | Output is correct |
16 | Correct | 16 ms | 23788 KB | Output is correct |
17 | Correct | 16 ms | 23788 KB | Output is correct |
18 | Correct | 16 ms | 23788 KB | Output is correct |
19 | Correct | 16 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 17 ms | 23788 KB | Output is correct |
22 | Correct | 17 ms | 23788 KB | Output is correct |
23 | Correct | 16 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 16 ms | 23788 KB | Output is correct |
26 | Correct | 17 ms | 23916 KB | Output is correct |
27 | Correct | 16 ms | 23916 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 17 ms | 23916 KB | Output is correct |
31 | Correct | 17 ms | 23916 KB | Output is correct |
32 | Correct | 17 ms | 23916 KB | Output is correct |
33 | Correct | 17 ms | 23916 KB | Output is correct |
34 | Correct | 16 ms | 23788 KB | Output is correct |
35 | Correct | 17 ms | 23916 KB | Output is correct |
36 | Correct | 17 ms | 23916 KB | Output is correct |
37 | Correct | 17 ms | 23916 KB | Output is correct |
38 | Correct | 17 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 18 ms | 23916 KB | Output is correct |
41 | Correct | 17 ms | 23916 KB | Output is correct |
42 | Correct | 17 ms | 23916 KB | Output is correct |
43 | Execution timed out | 5066 ms | 23788 KB | Time limit exceeded |
44 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23788 KB | Output is correct |
2 | Correct | 16 ms | 23788 KB | Output is correct |
3 | Correct | 16 ms | 23788 KB | Output is correct |
4 | Correct | 16 ms | 23788 KB | Output is correct |
5 | Correct | 16 ms | 23788 KB | Output is correct |
6 | Correct | 16 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 16 ms | 23788 KB | Output is correct |
9 | Correct | 16 ms | 23788 KB | Output is correct |
10 | Correct | 16 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 | 17 ms | 23788 KB | Output is correct |
14 | Correct | 17 ms | 23892 KB | Output is correct |
15 | Correct | 16 ms | 23788 KB | Output is correct |
16 | Correct | 16 ms | 23788 KB | Output is correct |
17 | Correct | 16 ms | 23788 KB | Output is correct |
18 | Correct | 16 ms | 23788 KB | Output is correct |
19 | Correct | 16 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 17 ms | 23788 KB | Output is correct |
22 | Correct | 17 ms | 23788 KB | Output is correct |
23 | Correct | 16 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 16 ms | 23788 KB | Output is correct |
26 | Correct | 17 ms | 23916 KB | Output is correct |
27 | Correct | 16 ms | 23916 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 17 ms | 23916 KB | Output is correct |
31 | Correct | 17 ms | 23916 KB | Output is correct |
32 | Correct | 17 ms | 23916 KB | Output is correct |
33 | Correct | 17 ms | 23916 KB | Output is correct |
34 | Correct | 16 ms | 23788 KB | Output is correct |
35 | Correct | 17 ms | 23916 KB | Output is correct |
36 | Correct | 17 ms | 23916 KB | Output is correct |
37 | Correct | 17 ms | 23916 KB | Output is correct |
38 | Correct | 17 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 18 ms | 23916 KB | Output is correct |
41 | Correct | 17 ms | 23916 KB | Output is correct |
42 | Correct | 17 ms | 23916 KB | Output is correct |
43 | Execution timed out | 5066 ms | 23788 KB | Time limit exceeded |
44 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 16 ms | 23788 KB | Output is correct |
2 | Correct | 16 ms | 23788 KB | Output is correct |
3 | Correct | 16 ms | 23788 KB | Output is correct |
4 | Correct | 16 ms | 23788 KB | Output is correct |
5 | Correct | 16 ms | 23788 KB | Output is correct |
6 | Correct | 16 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 16 ms | 23788 KB | Output is correct |
9 | Correct | 16 ms | 23788 KB | Output is correct |
10 | Correct | 16 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 | 17 ms | 23788 KB | Output is correct |
14 | Correct | 17 ms | 23892 KB | Output is correct |
15 | Correct | 16 ms | 23788 KB | Output is correct |
16 | Correct | 16 ms | 23788 KB | Output is correct |
17 | Correct | 16 ms | 23788 KB | Output is correct |
18 | Correct | 16 ms | 23788 KB | Output is correct |
19 | Correct | 16 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 17 ms | 23788 KB | Output is correct |
22 | Correct | 17 ms | 23788 KB | Output is correct |
23 | Correct | 16 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 16 ms | 23788 KB | Output is correct |
26 | Correct | 17 ms | 23916 KB | Output is correct |
27 | Correct | 16 ms | 23916 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 17 ms | 23916 KB | Output is correct |
31 | Correct | 17 ms | 23916 KB | Output is correct |
32 | Correct | 17 ms | 23916 KB | Output is correct |
33 | Correct | 17 ms | 23916 KB | Output is correct |
34 | Correct | 16 ms | 23788 KB | Output is correct |
35 | Correct | 17 ms | 23916 KB | Output is correct |
36 | Correct | 17 ms | 23916 KB | Output is correct |
37 | Correct | 17 ms | 23916 KB | Output is correct |
38 | Correct | 17 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 18 ms | 23916 KB | Output is correct |
41 | Correct | 17 ms | 23916 KB | Output is correct |
42 | Correct | 17 ms | 23916 KB | Output is correct |
43 | Execution timed out | 5066 ms | 23788 KB | Time limit exceeded |
44 | Halted | 0 ms | 0 KB | - |