Submission #964543

#	Time	Username	Problem	Language	Result	Execution time	Memory
964543		UmairAhmadMirza	Traffic (IOI10_traffic)	C++14	100 / 100	1047 ms	170680 KiB

traffic

// #pragma once 

#include <bits/stdc++.h>
#include "traffic.h"
using namespace std;
int const NN=1e6+5;
int fans[NN];
vector<int> adj[NN];
int sub[NN];
int ans=2000000001;
int arne=0;
void reroot(int a,int b){
	sub[a]-=sub[b];
	sub[b]+=sub[a];
}
void dfs(int node,int par){
	int mx=0;
	for(auto i:adj[node])
		mx=max(sub[i],mx);
	if(mx<ans){
		arne=node;
		ans=mx;
	}
	for(auto i:adj[node])
		if(i!=par){
			reroot(node,i);
			dfs(i,node);
			reroot(i,node);
		}
}
void cal_sub(int node,int par){
	for(auto i:adj[node]){
		if(i!=par){
			cal_sub(i,node);
			sub[node]+=sub[i];
		}
	}
	sub[node]+=fans[node];
}
int LocateCentre(int N, int P[], int S[], int D[]){
	for (int i = 0; i <N; ++i)
		fans[i]=P[i];
	for (int i = 0; i < N-1; ++i)
	{
		adj[S[i]].push_back(D[i]);
		adj[D[i]].push_back(S[i]);
	}
	cal_sub(0,-1);
	dfs(0,-1);
	return arne;
}

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