Submission #650233

#	Time	Username	Problem	Language	Result	Execution time	Memory
650233		Genius3435	Traffic (IOI10_traffic)	C++17	100 / 100	3080 ms	223128 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;


const int maxn = 1'000'005;
vector<int> adj[maxn];
unordered_map<ll, int> sz;
int a[maxn]; ll n;

inline int dfs(int es, int en) {
	const ll ind = es*n+en;
	if (sz.count(ind))
		return sz[ind];
	int s = a[en];
	for (const int &j: adj[en])
		if (j != es) s += dfs(en, j);
	return sz[ind] = s;
}

int LocateCentre(int N, int* P, int* S, int* D) {
	n = N;
	
	for (int i = 0; i < n; ++i)
		a[i] = P[i];
	
	for (int i = 0; i < n-1; ++i) {
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
	}
	
	int mn = 2e9, mi = -1;
	for (int i = 0, c = 0; i < n; ++i, c = 0) {
		for (const int &j: adj[i])
			c = max(c, dfs(i, j));
		if (c < mn) mn = c, mi = i;
	} return mi;
}

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