Submission #590711

#	Time	Username	Problem	Language	Result	Execution time	Memory
590711		l_reho	Traffic (IOI10_traffic)	C++14	100 / 100	1186 ms	237324 KiB

traffic

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

vector<long long> st;
vector<vector<int>> graph;
vector<bool> visited;
vector<int> parent;

long long preprocess(int curr, int pp[]){
	visited[curr] = true;
	vector<int> adj = graph[curr];
	st[curr] = pp[curr];
	for(int a : adj){
		if(visited[a]) continue;
		parent[a] = curr;
		st[curr] += preprocess(a, pp);	
	}
	return st[curr];
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	
	visited.assign(N, 0);
	parent.assign(N, 0);
	
	st.assign(N, 0LL);
	graph.assign(N, vector<int>());
	
	for(int i = 0; i < N-1; i++){
		graph[S[i]].push_back(D[i]);
		graph[D[i]].push_back(S[i]);
	}
	
	preprocess(0, pp);
	// for(int i = 0; i < N; i++) cout<<"DEBUG-->"<<st[i]<<endl;
	long long mn = LLONG_MAX;
	int ans = -1;
	
	for(int i = 0; i < N; i++){	
		vector<int> adj = graph[i];
		long long mx = -1;
		
		for(int a : adj){
			if(a != parent[i]){
				if(st[a] > mx) mx = st[a];
			}else {
				// calcolo della congestione della strada che collega 
				// i al parent
				
				long long cong = st[0] - st[i];
				// cout<<i<<" "<<a<<" "<<cong<<endl;
				if(cong > mx) mx = cong;
				
			}
		}
		if(mx < mn)
			ans = i;
		mn = min(mn, mx);
	}
	
	return ans;
}

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