Submission #409366

#	Time	Username	Problem	Language	Result	Execution time	Memory
409366		MrFrancho	Traffic (IOI10_traffic)	C++11	100 / 100	1119 ms	170820 KiB

traffic

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

#define pb push_back

using ll = long long;

const int MAXN = 1e6;

vector<int> adj[MAXN], children(MAXN), people(MAXN);
int totalFans = 0;

void DFS(int node, int father, int pp[]) {

	for(auto x: adj[node]) {
		if(x != father) {
			DFS(x,node,pp);
			children[node] += children[x];
			people[node] = max(people[node], children[x]);
		}
	}

	children[node] += pp[node];

	people[node] = max(people[node], totalFans - children[node]);
}

int LocateCentre(int N, int pp[], int S[], int D[]) {
	for(int i = 0; i < N; i++) {
		totalFans += pp[i];
	}

	for(int i = 0; i < N-1; i++) {
		adj[S[i]].pb(D[i]);
		adj[D[i]].pb(S[i]);
	}

	DFS(0,-1,pp);

	int sum = 2e9+1, bestCity;
 	for(int i = 0; i < N; i++) {
 		if(people[i] < sum) {
 			sum = people[i];
 			bestCity = i;
 		}
 	}

	return bestCity;
}

Compilation message (stderr)

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

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