Submission #888619

#	Time	Username	Problem	Language	Result	Execution time	Memory
888619		Muhammad_Aneeq	Traffic (IOI10_traffic)	C++17	100 / 100	736 ms	170064 KiB

traffic

#include <vector>
#include <algorithm>
using namespace std;
long long const MAXN=1e6+10;
vector<long long>nei[MAXN]={};
long long cost[MAXN],val1[MAXN];
int ans=0,z=2e9+10;
int y=0;
void dfs(int n,int m=-1)
{
	val1[n]+=cost[n];
	int x=0;
	for (auto i:nei[n])
	{
		if (i!=m)
		{
			dfs(i,n);
			val1[n]+=val1[i];
		}
	}
	long long f=-1;
	for (auto i:nei[n])
	{
		if (i==m)
			f=max(f,y-val1[n]);
		else
			f=max(f,val1[i]);
	}
	if (f!=-1&&f<z)
	{
		z=f;
		ans=n;
	}
}
int LocateCentre(int N,int P[1000000],int S[1000000],int D[1000000])
{
	for (int i=0;i<N;i++)
	{
		cost[i]=P[i];
		y+=cost[i];
	}
	for (int i=0;i<N-1;i++)
	{
		nei[S[i]].push_back(D[i]);
		nei[D[i]].push_back(S[i]);
	}
	dfs(0);
	return ans;
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:12:6: warning: unused variable 'x' [-Wunused-variable]
   12 |  int x=0;
      |      ^

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