# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
775594 | 2023-07-06T14:47:52 Z | DobromirAngelov | Traffic (IOI10_traffic) | C++14 | 14 ms | 23820 KB |
#include<bits/stdc++.h> #include "traffic.h" using namespace std; const int MAXN=1e6+5; const int INF=2e9+5; int a[MAXN]; vector<int> adj[MAXN]; int subtr[MAXN]; int dfs(int v,int par) { subtr[v]=a[v]; for(int i=0;i<adj[v].size();i++) { if(adj[v][i]==par) continue; subtr[v]+=dfs(adj[v][i], v); } return subtr[v]; } int LocateCentre(int n,int w[],int u[],int v[]) { for(int i=0;i<n;i++) a[i]=w[i]; for(int i=0;i<n-1;i++) { adj[u[i]].push_back(v[i]); adj[v[i]].push_back(u[i]); } dfs(0,-1); int ans=-1, best=INF; for(int i=0;i<n;i++) { int curMax=subtr[0]-subtr[i]; for(int j=0;j<adj[i].size();j++) { curMax=max(curMax, subtr[adj[i][j]]); } if(curMax<best) { best=curMax; ans=i; } } return ans; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23736 KB | Output is correct |
2 | Correct | 12 ms | 23820 KB | Output is correct |
3 | Incorrect | 12 ms | 23764 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23736 KB | Output is correct |
2 | Correct | 12 ms | 23820 KB | Output is correct |
3 | Incorrect | 12 ms | 23764 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23736 KB | Output is correct |
2 | Correct | 12 ms | 23820 KB | Output is correct |
3 | Incorrect | 12 ms | 23764 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 14 ms | 23736 KB | Output is correct |
2 | Correct | 12 ms | 23820 KB | Output is correct |
3 | Incorrect | 12 ms | 23764 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |