Submission #1265100

#	Time	Username	Problem	Language	Result	Execution time	Memory
1265100		Jer	Traffic (IOI10_traffic)	C++20	100 / 100	422 ms	149152 KiB

traffic

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

using namespace std;

const int MAXN = 1e6 + 5;
vector<int> con[MAXN];
int p[MAXN];
int n, res = INT_MAX, best = -1;
int total = 0;

int find(int i, int par)
{
	int sum = 0, most = 0;

	for (auto j : con[i])
	{
		if (j == par)
			continue;
		int r = find(j, i);
		sum += r, most = max(most, r);
	}

	sum += p[i];
	most = max(most, total - sum);

	if (most < res)
		best = i, res = most;

	return sum;
}

int LocateCentre(int N, int P[], int S[], int D[])
{
	n = N;
	for (int i = 0; i < n - 1; i++)
		con[S[i]].push_back(D[i]), con[D[i]].push_back(S[i]);

	for (int i = 0; i < n; i++)
		total += P[i], p[i] = P[i];

	find(0, 0);

	return best;
}

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