Submission #404462

#	Time	Username	Problem	Language	Result	Execution time	Memory
404462		Drew_	Traffic (IOI10_traffic)	C++17	100 / 100	1131 ms	123652 KiB

traffic

#include "traffic.h"
#include <iostream>
#include <vector>
#include <functional>
using namespace std;

#define pb push_back
#define ll long long

const int MAX = 1e6 + 7;

ll sz[MAX];
vector<int> adj[MAX];

inline ll dfs(int node, int par)
{
	for (int to : adj[node])
		if (to != par)
			sz[node] += dfs(to, node);
	return sz[node];
}

int LocateCentre(int N, int P[], int S[], int D[])
{
	for (int i = 0; i < N-1; ++i)
		adj[S[i]].pb(D[i]), adj[D[i]].pb(S[i]);
	for (int i = 0; i < N; ++i)
		sz[i] = P[i];
	dfs(0, -1);

	int res = -1;
	ll best = 1e18;
	for (int node = 0; node < N; ++node)
	{
		ll tmp = 0;
		for (int to : adj[node])
		{
			ll ctr = sz[to];
			if (sz[to] > sz[node])
				ctr = sz[0] - sz[node];
			tmp = max(tmp, ctr);
		}

		if (best > tmp)
			best = tmp, res = node;
	}
	return res;
}

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