제출 #371307

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
371307		NachoLibre	Traffic (IOI10_traffic)	C++17	100 / 100	1224 ms	147336 KiB

traffic

#include <bits/stdc++.h>
using namespace std;
#define sz(a) ((int)(a).size())
typedef vector<int> vint;
typedef vector<vint> vvint;
typedef long long ll;
#ifndef wambule
// #include ".h"
#else
#endif

const int inf = 2e9;
const int N = 1000006;
int *p, a, fp = inf, fw;
vector<int> v[N];

int sgd(int x, int op) {
	int z = p[x], m = 0, t;
	for(int y : v[x]) {
		if(y != op) {
			z += (t = sgd(y, x));
			m = max(m, t);
		}
	}
	m = max(m, a - z);
	if(fp > m) {
		fp = m;
		fw = x;
	}
	return z;
}

int LocateCentre(int n, int _p[], int x[], int y[]) {
	p = _p;
	for(int i = 0; i < n; ++i) {
		a += p[i];
	}
	for(int i = 0; i < n - 1; ++i) {
		v[x[i]].push_back(y[i]);
		v[y[i]].push_back(x[i]);
	}
	sgd(0, -1);
	return fw;
}

#ifdef wambule
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	return 0;
}
#endif

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