Submission #356813

#	Time	Username	Problem	Language	Result	Execution time	Memory
356813		Mefarnis	Traffic (IOI10_traffic)	C++14	100 / 100	1346 ms	180076 KiB

traffic

#include <bits/stdc++.h>
#include "traffic.h"
#define maxn 1000000
#define pb push_back
using namespace std;
typedef long long LL;

int ar[maxn];
LL sum[maxn];
LL ans[maxn];
vector<int> adj[maxn];

LL dfs(int u , int dad , int d) {
	sum[u] = ar[u];
	ans[0] += (LL) d * ar[u];
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i];
		if(v == dad)
			continue;
		sum[u] += dfs(v,u,d+1);
	}
	return sum[u];
}

void solve(int u , int dad) {
	int deg = adj[u].size();
	for( int i = 0 ; i < deg ; i++ ) {
		int v = adj[u][i];
		if(v == dad)
			continue;
		ans[v] = ans[u] + sum[0] - 2*sum[v];
		solve(v,u);
	}
}

int LocateCentre(int n, int P[], int S[], int D[]) {
	for( int i = 0 ; i < n ; i++ )
		ar[i] = P[i];
	for( int i = 0 ; i < n-1 ; i++ ) {
		int u = S[i] , v = D[i];
		adj[u].pb(v);
		adj[v].pb(u);
	}
	dfs(0,-1,0);
	solve(0,-1);
	int best = 0;
	for( int i = 1 ; i < n ; i++ )
		if(ans[i] < ans[best])
			best = i;
	return best;
}

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