Submission #1288237

#	Time	Username	Problem	Language	Result	Execution time	Memory
1288237		Jawad_Akbar_JJ	Traffic (IOI10_traffic)	C++20	100 / 100	713 ms	169284 KiB

traffic

#include <iostream>
#include <vector>

using namespace std;
#define Int long long
const Int M = 1<<20;
vector<Int> nei[M];
Int Mx[M], Pop[M], cst[M], Ans, maxAns = 1e17;

void dfs(Int u, Int p){
	cst[u] = Pop[u];
	for (Int i : nei[u]){
		if (i == p)
			continue;
		dfs(i, u);
		cst[u] += cst[i];
		Mx[u] = max(Mx[u], cst[i]);
	}
}

void dfs2(Int u, Int p){
	if (max(Mx[u], cst[p]) < maxAns)
		Ans = u, maxAns = max(Mx[u], cst[p]);

	for (Int i : nei[u]){
		if (i == p)
			continue;
		cst[u] += cst[p] - cst[i];
		dfs2(i, u);
		cst[u] += cst[i] - cst[p];
	}
}

int LocateCentre(int n, int p[], int s[], int d[]){
	for (Int i=0;i<n-1;i++){
		s[i]++;
		d[i]++;
		nei[s[i]].push_back(d[i]);
		nei[d[i]].push_back(s[i]);
	}

	for (Int i=0;i<n;i++)
		Pop[i+1] = p[i];

	dfs(1, 0);
	dfs2(1, 0);

	return Ans - 1;
}

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