Submission #395604

#	Time	Username	Problem	Language	Result	Execution time	Memory
395604		garnab27	Traffic (IOI10_traffic)	C++17	100 / 100	1409 ms	176640 KiB

traffic

#include <bits/stdc++.h>
#define ll int64_t
using namespace std;

vector<ll > sum;
vector<ll > ans;
vector<int> g[1000006];

ll dfs1(int u, int p, int pp[]) {
	sum[u] += pp[u];

	for(int v: g[u]) {
		if(v != p) {
			sum[u] += dfs1(v, u, pp);
		} 
	}

	return sum[u];
}

void dfs2(int u, int p, ll psum, int pp[]) {

	ans[u] = 0;
	ll csum = pp[u];
	if(p != -1) {
		ans[u] = max(ans[u], psum);
		csum += psum;
	}
	for(int v: g[u]) {
		if(v != p) {
			csum += sum[v];
			ans[u] = max(ans[u], sum[v]);
		}
	}
	for(int v: g[u]) {
		if(v != p) {
			dfs2(v, u, csum - sum[v], pp);
		}
	}
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
   	
   	sum.resize(N);
   	ans.resize(N);
   	for(int i=0;i<N-1;i++) {
   		g[S[i]].push_back(D[i]);
   		g[D[i]].push_back(S[i]);
   	}
   	dfs1(0, -1, pp);
   	dfs2(0, -1, 0, pp);
   	int id = 0, mn = ans[0];
   	for(int i=1;i<N;i++) {
   		if(mn > ans[i]) {
   			mn = ans[i];
   			id = i;
   		}
   	}
   	return id;
}

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