# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
377994 | 2021-03-15T17:11:33 Z | meperdonas203 | Traffic (IOI10_traffic) | C++17 | 48 ms | 48108 KB |
#include "traffic.h" #include <bits/stdc++.h> #include <vector> using namespace std; vector <int> adjacencia[1000002]; int sub_arb[1000002]; int menor=INT_MAX; int ans=0; int dfs(int nodo,int anterior){ for(int i=0;i<adjacencia[nodo].size();i++){ if(adjacencia[nodo][i]!=anterior){ sub_arb[nodo]+=dfs(adjacencia[nodo][i],nodo); } } return sub_arb[nodo]; } void respuesta(int nodo,int anterior){ int maximo=sub_arb[adjacencia[nodo][0]]; int hijo=adjacencia[nodo][0]; for(int i=0;i<adjacencia[nodo].size();i++){ if(sub_arb[adjacencia[nodo][i]]>maximo){ hijo=adjacencia[nodo][i]; maximo=sub_arb[adjacencia[nodo][i]]; } } if(maximo<menor){ ans=nodo; menor=maximo; } if(hijo==anterior){ return ; } sub_arb[nodo]-=sub_arb[hijo]; sub_arb[hijo]+=sub_arb[nodo]; respuesta(hijo,nodo); return; } int LocateCentre(int N, int pp[], int S[], int D[]) { for(int i=0;i<N;i++){ sub_arb[i]=pp[i]; } for(int i= 0;i<=N-2;i++){ adjacencia[S[i]].push_back(D[i]); adjacencia[D[i]].push_back(S[i]); } dfs(0,0); respuesta(0,0); return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23788 KB | Output is correct |
2 | Correct | 17 ms | 23936 KB | Output is correct |
3 | Correct | 17 ms | 23788 KB | Output is correct |
4 | Correct | 17 ms | 23788 KB | Output is correct |
5 | Correct | 18 ms | 23788 KB | Output is correct |
6 | Correct | 17 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 17 ms | 23916 KB | Output is correct |
9 | Correct | 17 ms | 23788 KB | Output is correct |
10 | Correct | 17 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 | 16 ms | 23788 KB | Output is correct |
15 | Correct | 19 ms | 23788 KB | Output is correct |
16 | Correct | 17 ms | 23916 KB | Output is correct |
17 | Correct | 17 ms | 23788 KB | Output is correct |
18 | Correct | 18 ms | 23788 KB | Output is correct |
19 | Correct | 17 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 18 ms | 23788 KB | Output is correct |
22 | Correct | 19 ms | 23788 KB | Output is correct |
23 | Correct | 17 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 17 ms | 23916 KB | Output is correct |
26 | Correct | 17 ms | 23936 KB | Output is correct |
27 | Correct | 17 ms | 24044 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 20 ms | 23916 KB | Output is correct |
31 | Correct | 19 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 | 17 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 | 20 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 17 ms | 23936 KB | Output is correct |
41 | Correct | 19 ms | 23916 KB | Output is correct |
42 | Correct | 18 ms | 23916 KB | Output is correct |
43 | Runtime error | 48 ms | 48108 KB | Execution killed with signal 11 |
44 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23788 KB | Output is correct |
2 | Correct | 17 ms | 23936 KB | Output is correct |
3 | Correct | 17 ms | 23788 KB | Output is correct |
4 | Correct | 17 ms | 23788 KB | Output is correct |
5 | Correct | 18 ms | 23788 KB | Output is correct |
6 | Correct | 17 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 17 ms | 23916 KB | Output is correct |
9 | Correct | 17 ms | 23788 KB | Output is correct |
10 | Correct | 17 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 | 16 ms | 23788 KB | Output is correct |
15 | Correct | 19 ms | 23788 KB | Output is correct |
16 | Correct | 17 ms | 23916 KB | Output is correct |
17 | Correct | 17 ms | 23788 KB | Output is correct |
18 | Correct | 18 ms | 23788 KB | Output is correct |
19 | Correct | 17 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 18 ms | 23788 KB | Output is correct |
22 | Correct | 19 ms | 23788 KB | Output is correct |
23 | Correct | 17 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 17 ms | 23916 KB | Output is correct |
26 | Correct | 17 ms | 23936 KB | Output is correct |
27 | Correct | 17 ms | 24044 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 20 ms | 23916 KB | Output is correct |
31 | Correct | 19 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 | 17 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 | 20 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 17 ms | 23936 KB | Output is correct |
41 | Correct | 19 ms | 23916 KB | Output is correct |
42 | Correct | 18 ms | 23916 KB | Output is correct |
43 | Runtime error | 48 ms | 48108 KB | Execution killed with signal 11 |
44 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23788 KB | Output is correct |
2 | Correct | 17 ms | 23936 KB | Output is correct |
3 | Correct | 17 ms | 23788 KB | Output is correct |
4 | Correct | 17 ms | 23788 KB | Output is correct |
5 | Correct | 18 ms | 23788 KB | Output is correct |
6 | Correct | 17 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 17 ms | 23916 KB | Output is correct |
9 | Correct | 17 ms | 23788 KB | Output is correct |
10 | Correct | 17 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 | 16 ms | 23788 KB | Output is correct |
15 | Correct | 19 ms | 23788 KB | Output is correct |
16 | Correct | 17 ms | 23916 KB | Output is correct |
17 | Correct | 17 ms | 23788 KB | Output is correct |
18 | Correct | 18 ms | 23788 KB | Output is correct |
19 | Correct | 17 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 18 ms | 23788 KB | Output is correct |
22 | Correct | 19 ms | 23788 KB | Output is correct |
23 | Correct | 17 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 17 ms | 23916 KB | Output is correct |
26 | Correct | 17 ms | 23936 KB | Output is correct |
27 | Correct | 17 ms | 24044 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 20 ms | 23916 KB | Output is correct |
31 | Correct | 19 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 | 17 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 | 20 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 17 ms | 23936 KB | Output is correct |
41 | Correct | 19 ms | 23916 KB | Output is correct |
42 | Correct | 18 ms | 23916 KB | Output is correct |
43 | Runtime error | 48 ms | 48108 KB | Execution killed with signal 11 |
44 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 17 ms | 23788 KB | Output is correct |
2 | Correct | 17 ms | 23936 KB | Output is correct |
3 | Correct | 17 ms | 23788 KB | Output is correct |
4 | Correct | 17 ms | 23788 KB | Output is correct |
5 | Correct | 18 ms | 23788 KB | Output is correct |
6 | Correct | 17 ms | 23788 KB | Output is correct |
7 | Correct | 18 ms | 23788 KB | Output is correct |
8 | Correct | 17 ms | 23916 KB | Output is correct |
9 | Correct | 17 ms | 23788 KB | Output is correct |
10 | Correct | 17 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 | 16 ms | 23788 KB | Output is correct |
15 | Correct | 19 ms | 23788 KB | Output is correct |
16 | Correct | 17 ms | 23916 KB | Output is correct |
17 | Correct | 17 ms | 23788 KB | Output is correct |
18 | Correct | 18 ms | 23788 KB | Output is correct |
19 | Correct | 17 ms | 23788 KB | Output is correct |
20 | Correct | 17 ms | 23788 KB | Output is correct |
21 | Correct | 18 ms | 23788 KB | Output is correct |
22 | Correct | 19 ms | 23788 KB | Output is correct |
23 | Correct | 17 ms | 23788 KB | Output is correct |
24 | Correct | 17 ms | 23788 KB | Output is correct |
25 | Correct | 17 ms | 23916 KB | Output is correct |
26 | Correct | 17 ms | 23936 KB | Output is correct |
27 | Correct | 17 ms | 24044 KB | Output is correct |
28 | Correct | 17 ms | 23916 KB | Output is correct |
29 | Correct | 17 ms | 23916 KB | Output is correct |
30 | Correct | 20 ms | 23916 KB | Output is correct |
31 | Correct | 19 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 | 17 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 | 20 ms | 23916 KB | Output is correct |
39 | Correct | 17 ms | 23916 KB | Output is correct |
40 | Correct | 17 ms | 23936 KB | Output is correct |
41 | Correct | 19 ms | 23916 KB | Output is correct |
42 | Correct | 18 ms | 23916 KB | Output is correct |
43 | Runtime error | 48 ms | 48108 KB | Execution killed with signal 11 |
44 | Halted | 0 ms | 0 KB | - |