Submission #411891

#	Time	Username	Problem	Language	Result	Execution time	Memory
411891		Berted	Traffic (IOI10_traffic)	C++14	100 / 100	1296 ms	153420 KiB

traffic

#include "traffic.h"
#include <vector>
#include <iostream>
#define vi vector<int>

using namespace std;

const int INF = 2000000100;

int A[1000001], DP[1000001];
vi adj[1000001];

int best = INF;
vi ans;

void DFS(int u, int p)
{
	DP[u] = A[u];
	for (const int &v : adj[u])
	{
		if (v == p) continue;
		DFS(v, u);
		DP[u] += DP[v];
	}
}

void DFS2(int u, int p, int w)
{
	int res = w;
	for (const int &v : adj[u])
	{
		if (v == p) continue;
		res = max(res, DP[v]);
	}

	if (res < best) {best = res; ans.clear();}
	if (res == best) ans.push_back(u);
	
	w += DP[u];
	for (const int &v : adj[u])
	{
		if (v == p) continue;
		DFS2(v, u, w - DP[v]);
	}
}

int LocateCentre(int N, int P[], int S[], int D[]) 
{
	for (int i = 0; i < N; i++) A[i] = P[i];
	for (int i = 0; i + 1 < N; i++)
	{
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
	}
	DFS(0, -1);
	DFS2(0, -1, 0);
	return ans[0];
}

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