# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
373486 | 2021-03-04T19:58:09 Z | eulerdesoja | Traffic (IOI10_traffic) | C++14 | 0 ms | 0 KB |
#include<bits/stdc++.h> #include<fstream> using namespace std; #define int long long #define pb push_back #define sz(x) int(x.size()) typedef pair<int,int>ii; typedef vector<int> vi; const int mxn=1e6+6; //maximum of congestion in a road vi g[mxn]; int ma[mxn],sum[mxn]; void dfs(int i,int p,int a[]){ for(int j:g[i])if(j!=p){ dfs(j,i,a); sum[i]+=sum[j]; ma[i]=max(ma[i],max(ma[j],sum[j])); } sum[i]+=a[i]; } int LocateCentre(int n,int a[],int s[],int d[]){ for(int i=0;i<n-1;i++){ g[s[i]].pb(d[i]); g[d[i]].pb(s[i]); } int ans=1e18,res; for(int i=0;i<n;i++){ memset(sum,0,sizeof(sum)); memset(ma,0,sizeof(ma)); dfs(i,-1,a); if(ma[i]<ans){ ans=ma[i]; res=i; } } return res; }