Submission #385001

#	Time	Username	Problem	Language	Result	Execution time	Memory
385001		ritul_kr_singh	Traffic (IOI10_traffic)	C++17	0 / 100	1 ms	364 KiB

traffic

#include <bits/stdc++.h>
// #include "traffic.h"
using namespace std;

const int MAXN = 1e6;
vector<vector<int>> g;
int sub[MAXN], sum = 0, x = 0, y = 0;
pair<int, int> ans = {(int)1e18, -1};

int dfs0(int u, int par){
	for(int v : g[u]) if(v != par){
			sub[u] += dfs0(v, u);
			x = max(x, sub[v]);
			if(x > y) swap(x, y);
	}
	return sub[u];
}

void dfs1(int u, int par){
	ans = min(ans, {y, u});
	for(int v : g[u]){
		if(v==par) continue;
		int px = x, py = y;
		if(sub[v]==y) y = 0;
		else if(sub[v]==x) x = 0;
		if(x > y) swap(x, y);

		x = max(x, sum - sub[v]);
		if(x > y) swap(x, y);
		dfs1(v, u);
		x = px, y = py;
	}
}

int LocateCentre(int n, int pop[], int S[], int D[]){
	for(int i=0; i<n; ++i) sum += (sub[i] = pop[i]);
	g.resize(n);
	for(int i=0; i<n-1; ++i){
		g[S[i]].push_back(D[i]);
		g[D[i]].push_back(S[i]);
	}
	dfs0(0, 0);
	dfs1(0, 0);
	return ans.second;
}

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