Submission #404876

#	Time	Username	Problem	Language	Result	Execution time	Memory
404876		Jasiekstrz	Traffic (IOI10_traffic)	C++17	100 / 100	1275 ms	164388 KiB

traffic

#include<bits/stdc++.h>
#include "traffic.h"
#define fi first
#define se second
using namespace std;
const int NN=1e6;
vector<int> e[NN+10];
int siz[NN+10];
void dfs_siz(int x,int p)
{
	for(auto v:e[x])
	{
		if(v!=p)
		{
			dfs_siz(v,x);
			siz[x]+=siz[v];
		}
	}
	return;
}
pair<int,int> dfs_min(int x,int p,int siz_all)
{
	pair<int,int> ans={0,x};
	for(auto v:e[x])
	{
		if(v==p)
			ans.fi=max(ans.fi,siz_all-siz[x]);
		else
			ans.fi=max(ans.fi,siz[v]);
	}
	for(auto v:e[x])
	{
		if(v!=p)
			ans=min(ans,dfs_min(v,x,siz_all));
	}
	return ans;
}
int LocateCentre(int N,int pp[],int S[],int D[])
{
	for(int i=0;i<N-1;i++)
	{
		e[S[i]].push_back(D[i]);
		e[D[i]].push_back(S[i]);
	}
	for(int i=0;i<N;i++)
		siz[i]=pp[i];
	dfs_siz(0,-1);
	return dfs_min(0,-1,siz[0]).se;
}

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