Submission #201895

#	Time	Username	Problem	Language	Result	Execution time	Memory
201895		luciocf	Traffic (IOI10_traffic)	C++14	100 / 100	1720 ms	152824 KiB

traffic

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

using namespace std;

const int maxn = 1e6+10;

int tot, mn, ans;
int a[maxn];

int sub[maxn];

vector<int> grafo[maxn];

void dfs(int u, int p)
{
	sub[u] = a[u];

	for (auto v: grafo[u])
	{
		if (v != p)
		{
			dfs(v, u);
			sub[u] += sub[v];
		}
	}
}

void solve(int u, int p)
{
	int aux = tot-sub[u];

	for (auto v: grafo[u])
	{
		if (v != p)
		{
			aux = max(aux, sub[v]);
			solve(v, u);
		}
	}

	if (aux < mn)
	{
		ans = u;
		mn = aux;
	}
}

int LocateCentre(int N, int P[], int S[], int D[])
{
	for (int i = 1; i <= N; i++)
		grafo[i].clear();

	for (int i = 1; i < N; i++)
	{
		S[i-1]++, D[i-1]++;

		grafo[S[i-1]].push_back(D[i-1]);
		grafo[D[i-1]].push_back(S[i-1]);
	}

	tot = 0;
	
	for (int i = 1; i <= N; i++)
	{
		a[i] = P[i-1];
		tot += a[i];
	}

	mn = tot;
	dfs(1, 0); solve(1, 0);

	return ans-1;
}

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