Submission #272095

#	Time	Username	Problem	Language	Result	Execution time	Memory
272095		TMJN	Traffic (IOI10_traffic)	C++17	100 / 100	1266 ms	149272 KiB

traffic

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

vector<int>v[1000000];
long long c[1000000],m[1000000];

void dfs(int x,int from){
	for(int i:v[x]){
		if(i==from)continue;
		dfs(i,x);
		c[x]+=c[i];
	}
}

int LocateCentre(int N, int P[], int S[], int D[]) {
	for(int i=0;i<N-1;i++){
		v[S[i]].push_back(D[i]);
		v[D[i]].push_back(S[i]);
	}
	for(int i=0;i<N;i++){
		c[i]=P[i];
	}
	dfs(0,0);
	for(int i=0;i<N-1;i++){
		if(c[S[i]]<c[D[i]])swap(S[i],D[i]);
		m[S[i]]=max(m[S[i]],c[D[i]]);
		m[D[i]]=max(m[D[i]],c[0]-c[D[i]]);
	}
	pair<long long,int>res={0xE869120E869120,-1};
	for(int i=0;i<N;i++){
		res=min(res,{m[i],i});
	}
	return res.second;
}

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