Submission #339071

#	Time	Username	Problem	Language	Result	Execution time	Memory
339071		study	Traffic (IOI10_traffic)	C++17	100 / 100	1511 ms	171096 KiB

traffic

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

const int NB = 1e6+1;

vector<int> subtree(NB);
vector<bool> vu(NB);
vector<int> ans(NB);

void dfs1(int node, vector<vector<int>>& adj, int pp[]){
	int sum = pp[node];
	for (int i:adj[node]){
		if (!vu[i]){
			vu[i] = true;
			dfs1(i,adj,pp);
			sum += subtree[i];
		}
	}
	subtree[node] = sum;
}

void dfs2(int node, vector<vector<int>>& adj){
	for (int i:adj[node]) ans[node] = max(ans[node],subtree[i]);
	for (int i:adj[node]){
		if (!vu[i]){
			vu[i] = true;
			int a = subtree[node], b = subtree[i];
			subtree[node] -= subtree[i];
			subtree[i] += subtree[node];
			dfs2(i,adj);
			subtree[node] = a;
			subtree[i] = b;
		}
	}
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	subtree = vector<int>(N);
	vu = vector<bool>(N);
	ans = vector<int>(N);
	vector<vector<int>> adj(N);
	for (int i=0; i<N-1; ++i){
		adj[S[i]].emplace_back(D[i]);
		adj[D[i]].emplace_back(S[i]);
	}
	vu[0] = true;
	dfs1(0,adj,pp);
   vu = vector<bool>(N);
	vu[0] = true;
   dfs2(0,adj);
	int mini = INT_MAX,idx=0;
	for (int i=0; i<N; ++i){
		if (mini > ans[i]){
			mini = ans[i];
			idx = i;
		}
	}
	return idx;
}

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