Submission #38929

#	Time	Username	Problem	Language	Result	Execution time	Memory
38929		14kg	Race (IOI11_race)	C++11	0 / 100	12 ms	14456 KiB

race

#include "race.h"
#include <vector>
#include <algorithm>
#include <set>
#define N 200001
#define M 1000001
#define INF 999999999

using namespace std;
int n, m, out=INF;
vector<pair<int, long long> > r[N];
set<int> prohibit[N];

int len, core, d_cnt[N], d[M];
bool check[N];

bool check_can(int x, int y) {
	set<int>::iterator it = prohibit[x].lower_bound(y);

	if (it == prohibit[x].end() || *it != y) return true;
	return false;
}
void find_len(int x) {
	check[x] = true, len++;
	for (auto i : r[x])
		if (check[i.first] == false && check_can(x, i.first)) find_len(i.first);
}
int find_cnt(int x, int up) {
	d_cnt[x] = 1;
	for (auto i : r[x])
		if (i.first != up && check_can(x, i.first)) d_cnt[x] += find_cnt(i.first, x);
	return d_cnt[x];
}
void find_core(int x, int up, int up_cnt) {
	bool core_check = true;

	if (up_cnt > len / 2) return;
	for(auto i:r[x])
		if (i.first != up && check_can(x, i.first)) {
			if (d_cnt[i.first] > len / 2) core_check = false;
			find_core(i.first, x, up_cnt + d_cnt[x] - d_cnt[i.first]);
		}
	if (core_check) core = x;
}
void f(int start) {
	len = 0, find_len(start);
	find_cnt(start, 0), find_core(start, 0, 0);

	int _core = core;
	for (auto i : r[_core])
		if (check_can(_core, i.first)) {
			prohibit[_core].insert(i.first);
			prohibit[i.first].insert(_core);
			f(i.first);
		}
}
int best_path(int _n, int _m, int in1[][2], int in2[]) {
	n = _n, m = _m;
	for (int i = 0; i < n - 1; i++) {
		int x = in1[i][0] + 1, y = in1[i][1] + 1;
		r[x].push_back({ y,(long long)in2[i] });
		r[y].push_back({ x,(long long)in2[i] });
	}

	f(1);
	return out == INF ? -1 : out;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57