Submission #308281

#	Time	Username	Problem	Language	Result	Execution time	Memory
308281		sofapuden	Traffic (IOI10_traffic)	C++14	100 / 100	1236 ms	148004 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

#define f first
#define s second

using namespace std;

vector<vector<int>> gra;
vector<int> chi, big, val;
pair<int,int> ans;

int tot = 0;

void dfs(int x, int p){
	for(int v : gra[x]){
		if(v == p)continue;
		dfs(v,x);
		chi[x] += chi[v];
		big[x] = max(big[x], chi[v]);
	}
	big[x] = max(big[x], tot-val[x]-chi[x]);
	chi[x] += val[x];
}

int LocateCentre(int n, int pp[], int s[], int d[]) {
	chi.resize(n,0);
	big.resize(n,0);
	gra.resize(n);
	for(int i = 0; i < n-1; ++i){
		gra[s[i]].push_back(d[i]);
		gra[d[i]].push_back(s[i]);
	}
	for(int i = 0; i < n; ++i){
		val.push_back(pp[i]);tot+=pp[i];
	}
	dfs(0,0);
	ans = {tot,-1};
	for(int i = 0; i < n; ++i){
		if(big[i] < ans.f){
			ans.f = big[i];
			ans.s = i;
		}
	}
	return ans.s;
	
	
		
}

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