Submission #981388

#	Time	Username	Problem	Language	Result	Execution time	Memory
981388		tamir1	Traffic (IOI10_traffic)	C++17	100 / 100	776 ms	176088 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll mx,pr[1000005],sum[1000005],s;
int loc;
vector<int> v[1000005];
void dfs(int a,int p){
	ll mx=0;
	for(int i:v[a]){
		if(i==p) continue;
		dfs(i,a);
		sum[a]+=sum[i];
		mx=max(mx,sum[i]);
	}
	pr[a]=mx;
}
int LocateCentre(int N, int pp[], int S[], int D[]) {
	mx=1e18;
	loc=-1;
	for(int i=0;i<N;i++){
		sum[i]=pp[i];
		s+=pp[i];
	}
	for(int i=0;i<N-1;i++){
		v[S[i]].push_back(D[i]);
		v[D[i]].push_back(S[i]);
	}
	dfs(0,-1);
	for(int i=0;i<N;i++){
		pr[i]=max(pr[i],s-sum[i]);
		if(pr[i]<mx){
			mx=pr[i];
			loc=i;
		}
	}
   return loc;
}

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