Submission #373496

#	Time	Username	Problem	Language	Result	Execution time	Memory
373496		eulerdesoja	Traffic (IOI10_traffic)	C++14	100 / 100	1352 ms	163564 KiB

traffic

#include<bits/stdc++.h>
#include<fstream>
using namespace std;

#define ll 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];
	}
	sum[i]+=a[i];
}
void dfs1(int i,int p){
	for(int j:g[i])if(j!=p){
		ma[i]=max(ma[i],sum[j]);
		dfs1(j,i);
	}
	ma[i]=max(ma[i],sum[0]-sum[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]);
	}
	dfs(0,-1,a);
	dfs1(0,-1);
	int ans=2e9+10,res=0;
	for(int i=0;i<n;i++){
		if(ma[i]<ans){
			ans=ma[i];
			res=i;
		}
	}
	return res;
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25