# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
222978 | 2020-04-14T12:39:38 Z | Lawliet | Traffic (IOI10_traffic) | C++14 | 20 ms | 23808 KB |
#include "traffic.h" #include "bits/stdc++.h" using namespace std; const int MAXN = 1000010; int n; int optNode; int optValue = MAXN; int sub[MAXN]; vector< int > adj[MAXN]; void DFSInit(int cur, int p) { for(int i = 0 ; i < adj[cur].size() ; i++) { int viz = adj[cur][i]; if( viz == p ) continue; DFSInit( viz , cur ); sub[cur] += sub[viz]; } } void DFSCalculate(int cur, int p) { int curValue = sub[0] - sub[cur]; for(int i = 0 ; i < adj[cur].size() ; i++) { int viz = adj[cur][i]; if( viz != p ) curValue = max( curValue , sub[viz] ); } if( curValue < optValue ) { optNode = cur; optValue = curValue; } for(int i = 0 ; i < adj[cur].size() ; i++) { int viz = adj[cur][i]; if( viz != p ) DFSCalculate( viz , cur ); } } int LocateCentre(int N, int P[], int S[], int D[]) { for(int i = 0 ; i < N ; i++) sub[i] = P[i]; for(int i = 0 ; i < N - 1 ; i++) { adj[ S[i] ].push_back( D[i] ); adj[ D[i] ].push_back( S[i] ); } DFSInit( 0 , 0 ); DFSCalculate( 0 , 0 ); return optNode; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23808 KB | Output is correct |
2 | Incorrect | 20 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23808 KB | Output is correct |
2 | Incorrect | 20 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23808 KB | Output is correct |
2 | Incorrect | 20 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 19 ms | 23808 KB | Output is correct |
2 | Incorrect | 20 ms | 23808 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |