Submission #199621

#	Time	Username	Problem	Language	Result	Execution time	Memory
199621		Markomafko972	Traffic (IOI10_traffic)	C++14	100 / 100	1599 ms	151032 KiB

traffic

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

vector<int> v[1000002];
int a[1000002];
long long sol[1000002];
long long maxi[1000002];

void dfs(int x, int prt) {
	for (int i = 0; i < v[x].size(); i++) {
		int sus = v[x][i];
		if (sus != prt) {
			dfs(sus, x);
			sol[x] += sol[sus];
			sol[x] += a[sus];
			maxi[x] = max(maxi[x], sol[sus]+a[sus]);
		}
	}
}

int LocateCentre(int n, int p[], int s[], int d[]) {
	long long zbr = 0;
	for (int i = 0; i < n; i++) a[i] = p[i], zbr += a[i];
	
	for (int i = 0; i < n-1; i ++) {
		v[s[i]].push_back(d[i]);
		v[d[i]].push_back(s[i]);
	}
	
	dfs(1, 0);
	long long mini = 1e18;
	int w = 0;
	
	for (int i = 0; i < n; i++) {
		maxi[i] = max(maxi[i], zbr-sol[i]-a[i]);
		if (maxi[i] < mini) {
			mini = maxi[i];
			w = i;
		}
	}
	
	return w;
}

Compilation message (stderr)

traffic.cpp: In function 'void dfs(int, int)':
traffic.cpp:10:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < v[x].size(); i++) {
                  ~~^~~~~~~~~~~~~

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