Submission #414129

#	Time	Username	Problem	Language	Result	Execution time	Memory
414129		O_o	Traffic (IOI10_traffic)	C++14	100 / 100	1202 ms	186444 KiB

traffic

#include "traffic.h"
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ld long double

#define rep(i,a,b) for(int i=a;i<b;i++)
#define repb(i,a,b) for(int i=a;i>=b;i--)

#define pb push_back
#define mp make_pair
#define all(A) A.begin(),A.end()
#define allr(A) A.rbegin(),A.rend()
#define precise(i) fixed << setprecision(i)
#define fi first
#define se second
#define sz(x) ((int)(x).size())

#define err() cout<<"\n==================================\n";
#define errA(A) for(auto i:A) cout<<i<<" "; cout<<"\n";
#define err1(a) cout<<#a<<" "<<a<<"\n";
#define err2(a,b) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<"\n";
#define err3(a,b,c) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<"\n";
#define err4(a,b,c,d) cout<<#a<<" "<<a<<" "<<#b<<" "<<b<<" "<<#c<<" "<<c<<" "<<#d<<" "<<d<<"\n";

#define Pii pair<int,int>
#define Vi vector<ll>
#define Vpii vector<Pii>

Vi adj[1000003];
Vi loc(1000003);
Vi ans(1000003);
Vi subtree(1000003);
ll tot;

void dfs(int x, int p)
{
	subtree[x]+= loc[x];
	for(auto e: adj[x])
	{
		if(e != p)
		{
			dfs(e, x);
			subtree[x]+= subtree[e];
			ans[x]= max(ans[x], subtree[e]);
		}
	}
	ans[x]= max(ans[x], tot-subtree[x]);
}

int LocateCentre(int n, int p[], int s[], int d[])
{
	tot= 0;
	rep(c,0,n)
	{
		loc[c]= p[c];
		tot+= p[c];
	}
	rep(c,0,n-1)
	{
		adj[s[c]].pb(d[c]);
		adj[d[c]].pb(s[c]);
	}
	dfs(0, -1);
	int res;
	ll val= 1e18;
	rep(c,0,n)
	{
		if(ans[c] < val)
		{
			res= c;
			val= ans[c];
		}
	}
	return res;
}

Compilation message (stderr)

traffic.cpp: In function 'int LocateCentre(int, int*, int*, int*)':
traffic.cpp:76:9: warning: 'res' may be used uninitialized in this function [-Wmaybe-uninitialized]
   76 |  return res;
      |         ^~~

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