Submission #373487

#	Time	Username	Problem	Language	Result	Execution time	Memory
373487		eulerdesoja	Traffic (IOI10_traffic)	C++14	50 / 100	5044 ms	39276 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];
		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=0;
	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;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:30:10: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   30 |  int ans=1e18,res=0;
      |          ^~~~

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