Submission #999354

#	Time	Username	Problem	Language	Result	Execution time	Memory
999354		ZeroCool	Traffic (IOI10_traffic)	C++14	100 / 100	736 ms	225104 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>

using namespace std;

#define ar array
#define ll long long
const int mxn = 2e6 + 20;

vector<int> g[mxn];
int sz[mxn], dp[mxn], A[mxn], ans[mxn];

void dfs1(int x,int p){
	sz[x] = A[x];
	dp[x] = 0;
	for(auto u: g[x]){
		if(u == p)continue;
		dfs1(u, x);
		sz[x] += sz[u];
		dp[x] = max(dp[x], sz[u]);
	}
}

void dfs2(int x,int p){
	ans[x] = dp[x];
	
	for(auto u: g[x]){
		if(u == p)continue;
		int osx = sz[x];
		int osu = sz[u];
		int odx = dp[x];
		int odu = dp[u];
		
		sz[x] -= sz[u];
		sz[u] += sz[x];
		dp[u] = max(dp[u], sz[x]);
		
		dfs2(u, x);
		
		sz[x] = osx;
		sz[u] = osu;
		dp[x] = odx;
		dp[u] = odu;
	}
}


int LocateCentre(int n, int pp[], int S[], int D[]) {
	for(int i = 0;i<n;i++)A[i] = pp[i];

	for(int i = 0;i< n-1;i++){
	   g[S[i]].push_back(D[i]);
	   g[D[i]].push_back(S[i]);
	}
   
   dfs1(0, 0);
   dfs2(0, 0);
   int mi = 0;
   for(int i =1;i<n;i++){
	   if(ans[i] < ans[mi])mi = i;
   }
   return mi;
}

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