Submission #522273

#	Time	Username	Problem	Language	Result	Execution time	Memory
522273		tkwiatkowski	Traffic (IOI10_traffic)	C++17	0 / 100	11 ms	23756 KiB

traffic

/*
	Zadanie: Traffic
	Autor: Tomasz Kwiatkowski
*/

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

using namespace std;

const int MAXN = 1e6 + 7;

vector<int> G[MAXN];
int dp[MAXN];

void DFS_dp(int v, int p)
{
	for (auto u : G[v]) {
		if (u != p) {
			DFS_dp(u, v);
			dp[v] += dp[u];
		}
	}
}

pair<int, int> DFS_move(int v, int p)
{
	pair<int, int> best = {0, 0};
	for (auto u : G[v])
		best = max(make_pair(dp[u], u), best);
	
	for (auto u : G[v]) {
		if (u != p) {
			dp[v] -= dp[u];
			dp[u] += dp[v];
			best = min(DFS_move(u, v), best);
			dp[u] -= dp[v];
			dp[v] += dp[u];
		}
	}
	return best;
}

int LocateCentre(int N, int P[], int S[], int D[])
{
	for (int i = 0; i < N-1; ++i)
		G[S[i]].pb(D[i]), G[D[i]].pb(S[i]);
	for (int i = 0; i < N; ++i)
		dp[i] = P[i];
	DFS_dp(0, 0);
	return DFS_move(0, 0).second;
}

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