제출 #38930

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
38930		14kg	경주 (Race) (IOI11_race)	C++11	100 / 100	1375 ms	65936 KiB

race

#include "race.h"
#include <vector>
#include <algorithm>
#include <set>
#define N 200001
#define M 1000001
#define INF 999999999
#define min2(x,y) (x<y?x:y)

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];
pair<int,int> 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, check[x] = false;
	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 Update(int x, int up, int tot_len, int cnt) {
	if (tot_len > m) return;

	if (d[m - tot_len].first == core) out = min2(out, cnt + d[m - tot_len].second);

	for (auto i : r[x])
		if (i.first != up && check_can(x, i.first)) Update(i.first, x, tot_len + i.second, cnt + 1);

}
void Push(int x, int up, int tot_len, int cnt) {
	if (tot_len > m) return;

	if (d[tot_len].first != core) d[tot_len] = { core,cnt };
	else if (d[tot_len].second > cnt) d[tot_len] = { core,cnt };
	
	for (auto i : r[x])
		if (i.first != up && check_can(x, i.first)) Push(i.first, x, tot_len + i.second, cnt + 1);

}
void f(int start) {
	len = 0, find_len(start);
	find_cnt(start, 0), find_core(start, 0, 0);

	d[0] = { core,0 };
	for (auto i : r[core])
		if (check_can(core, i.first)) {
			Update(i.first, core, i.second, 1);
			Push(i.first, core, i.second, 1);
		}

	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: 9 / 9
• Subtask 2: 12 / 12
• Subtask 3: 22 / 22
• Subtask 4: 57 / 57