Submission #309038

#	Time	Username	Problem	Language	Result	Execution time	Memory
309038		CaroLinda	Traffic (IOI10_traffic)	C++14	100 / 100	1455 ms	149752 KiB

traffic

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

#define sz(x) (int)(x.size())
#define debug printf
#define lp(i,a,b) for(int i = a ; i < b; i++)
#define pb push_back
#define ff first
#define ss second
#define mk make_pair
#define pii pair<int,int>
#define ll long long 
#define all(x) x.begin(),x.end()

const int MAX = 1e6+10 ;
const int inf = 2e9+10 ;

using namespace std ;

int mn = inf , idx ;
int sub[MAX] ;
vector<int> adj[MAX] ;
bool spun[MAX] ;

void dfs1(int x, int dad=-1)
{
	for(auto e : adj[x] ) 
		if(e != dad) 
		{
			dfs1(e, x) ;
			sub[x] += sub[e] ;
		}
}

void dfs2(int x)
{
	spun[x] = true ;

	int saveSub = sub[x] ;
	int myMx = 0 ;

	for(auto e : adj[x] ) 
		myMx = max(myMx , sub[e] ) ;


	if(myMx < mn )
	{
		mn = myMx ;
		idx = x ;
	}

	for(auto e : adj[x] ) 
	{
		if( spun[e] ) continue ;

		int saveE = sub[e] ;
		
		sub[x] -= sub[e]; 
		sub[e] = saveSub ;

		dfs2(e) ;

		sub[e] = saveE ;
		sub[x] = saveSub ;
	}
}

int LocateCentre(int N, int pp[], int S[], int D[]) 
{
	lp(i,0,N) sub[i] += pp[i] ;
	lp(i,0,N-1)
	{
		int u = S[i] ;
		int v = D[i] ;

		adj[u].pb(v) ;
		adj[v].pb(u) ;

	}

	dfs1(0,-1) ;
	dfs2(0) ;

	return idx ;
}

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