# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
400308 | 2021-05-07T20:39:35 Z | Pichon5 | Traffic (IOI10_traffic) | C++17 | 3 ms | 2636 KB |
#include<bits/stdc++.h> #include "traffic.h" #define pb push_back #define vi vector<int> #define ll long long using namespace std; const int tam=1e5; vector<int> G[tam]; ll peso[tam]; ll tot[tam];//suma de todos sus hijos ll dp[tam];//maximo de sus hijos ll sum=0; int ind; ll mi=1e18; void dfs(int nodo, int p){ for(int i=0;i<G[nodo].size();i++){ int it=G[nodo][i]; if(it==p)continue; dfs(it,nodo); tot[nodo]+=tot[it]; dp[nodo]=max(dp[nodo],tot[nodo]); } ll aux=max(dp[nodo],sum-tot[nodo]); if(aux<mi){ ind=nodo; mi=aux; } } int LocateCentre(int N, int pp[], int S[], int D[]) { for(int i=0;i<N;i++){ peso[i]=pp[i];sum+=pp[i];tot[i]=peso[i]; } for(int i=0;i<N-1;i++){ int a=S[i],b=D[i]; G[a].pb(b);G[b].pb(a); //cout<<a<<" unido "<<b<<endl; } dfs(0,-1); return ind; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 3 ms | 2636 KB | Output is correct |
4 | Incorrect | 3 ms | 2636 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 3 ms | 2636 KB | Output is correct |
4 | Incorrect | 3 ms | 2636 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 3 ms | 2636 KB | Output is correct |
4 | Incorrect | 3 ms | 2636 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 2 ms | 2636 KB | Output is correct |
2 | Correct | 2 ms | 2636 KB | Output is correct |
3 | Correct | 3 ms | 2636 KB | Output is correct |
4 | Incorrect | 3 ms | 2636 KB | Output isn't correct |
5 | Halted | 0 ms | 0 KB | - |