Submission #888613

#	Time	Username	Problem	Language	Result	Execution time	Memory
888613		Muhammad_Aneeq	Traffic (IOI10_traffic)	C++17	0 / 100	7 ms	29020 KiB

traffic

#include <vector>
#include <algorithm>
using namespace std;
int const MAXN=1e6+10;
vector<int>nei[MAXN]={};
int val[MAXN]={};
vector<int>z;
int dfs(int n,int root,int m=-1)
{
	int ans=0;
	for (auto i:nei[n])
	{
		if (i!=m)
		{
			int x=dfs(i,root,n)+val[i];
			ans+=x;
			if (n==root)
				z.push_back(x);
		}
	}
	return ans;
}
int LocateCentre(int N,int P[1000000],int S[1000000],int D[1000000])
{
	bool w=1;
	for (int i=0;i<N-1;i++)
	{
		nei[S[i]].push_back(D[i]);
		nei[D[i]].push_back(S[i]);
		if (S[i]+1!=D[i])
			w=0;
	}
	if (w==1)
	{
		int f=0;
		for (int i=0;i<N;i++)
			f+=P[i];
		int ans=0,z=2e9+10,cur=0;
		for (int i=0;i<N;i++)
		{
			f-=P[i];
			if (abs(f-cur)<z)
			{
				z=abs(f-cur);
				ans=i;
			}
			cur+=P[i];
		}
		return ans;
	}
	for (int i=0;i<N;i++)
		val[i]=P[i];
	int ans=0,f=2e9+10;
	for (int i=0;i<N;i++)
	{
		dfs(i,i);
		if (z.size()<2)
			z.push_back(0);
		sort(begin(z),end(z));
		if (z.back()-z[0]<f)
		{
			f=z.back()-z[0];
			ans=i;
		}
		z={};
	}
	return ans;
}

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