제출 #991855

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
991855		phoenix	Race (IOI11_race)	C++17	100 / 100	262 ms	34644 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 200200;
const int L = 2000000;
const int INF = 1e9;

struct edge {
	int to;
	int w;
};	

int n, k;

int sz[N];
bool rmv[N];
vector<edge> g[N];

int calc(int s, int p) {
	sz[s] = 1;
	for (auto [to, w] : g[s]) {
		if (to == p || rmv[to]) continue;
		sz[s] += calc(to, s);
	} 
	return sz[s];
}

int find_centroid(int s, int p, int m) {
	for (auto [to, w] : g[s]) {
		if (to == p || rmv[to]) continue;
		if (sz[to] * 2 > m)
			return find_centroid(to, s, m);
	}
	return s;
}

int answer;
int mp[L];

void get_answer(int s, int p, int dep, int len) {
	if (len <= k)
		answer = min(answer, mp[k - len] + dep);
	for (auto [to, w] : g[s]) {
		if (to == p || rmv[to]) continue;
		get_answer(to, s, dep + 1, len + w);
	}
}

void add_to_map(int s, int p, int dep, int len) {
	if (len <= k)
		mp[len] = min(mp[len], dep);
	for (auto [to, w] : g[s]) {
		if (to == p || rmv[to]) continue;
		add_to_map(to, s, dep + 1, len + w);
	}
}

void clear_map(int s, int p, int dep, int len) {
	if (len <= k)
		mp[len] = INF;
	for (auto [to, w] : g[s]) {
		if (to == p || rmv[to]) continue;
		clear_map(to, s, dep + 1, len + w);
	}
}


void decompose(int s) {
	int C = find_centroid(s, s, calc(s, s));

	mp[0] = 0;
	for (auto [to, w] : g[C]) {
		if (rmv[to]) continue;
		get_answer(to, C, 1, w);
		add_to_map(to, C, 1, w);
	}
	for (auto [to, w] : g[C]) {
		if (rmv[to]) continue;
		clear_map(to, C, 1, w);
	}
	mp[0] = INF;

	rmv[C] = true;
	for (auto [to, w] : g[C]) {
		if (!rmv[to])
			decompose(to);
	}
}


int best_path(int n_inside, int k_inside, int H[][2], int L[]) {	
	n = n_inside;
	k = k_inside;
	for (int i = 0; i < n - 1; i++) {
		g[H[i][0]].push_back({H[i][1], L[i]});
		g[H[i][1]].push_back({H[i][0], L[i]});
	}

	answer = INF;
	for (int x = 0; x <= k; x++)
		mp[x] = INF;

	decompose(1);
	if (answer == INF)
		return -1;
	return answer;
}

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