Submission #784641

#	Time	Username	Problem	Language	Result	Execution time	Memory
784641		faruk	Race (IOI11_race)	C++17	100 / 100	474 ms	27756 KiB

race

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

using namespace std;

typedef pair<int, int> pii;

int n, k;
vector<vector<pii> > graph;
vector<bool> marked;
vector<int> sz;
int min_len = 1e9;

int find_centroid(int curr, int par, int all) {
	for (auto &[a, w] : graph[curr])
		if (a != par and !marked[a] and sz[a] * 2 > all)
			return find_centroid(a, curr, all);
	return curr;
}

vector<int> min_length_for_siz;
void reset_mlfs(int curr, int par, int depth) {
	sz[curr] = 0;
	if (depth > k)
		return;
	min_length_for_siz[depth] = 1e9;
	sz[curr] = 1;
	for (auto &[a, w] : graph[curr])
		if (!marked[a] and a != par)
			reset_mlfs(a, curr, depth + w), sz[curr] += sz[a];
}

void update_mlfs(int curr, int par, int depth, int len) {
	if (depth > k)
		return;
	min_length_for_siz[depth] = min(min_length_for_siz[depth], len);
	for (auto &[a, w] : graph[curr])
		if (!marked[a] and a != par)
			update_mlfs(a, curr, depth + w, len + 1);
}

void update_k(int curr, int par, int depth, int len) {
	if (depth > k)
		return;
	min_len = min(min_len, len + min_length_for_siz[k-depth]);
	for (auto &[a, w] : graph[curr])
		if (!marked[a] and a != par)
			update_k(a, curr, depth + w, len + 1);
}

void dfs(int curr) {
	reset_mlfs(curr, 0, 0);
	int cent = find_centroid(curr, 0, sz[curr]);
	marked[cent] = true;
	min_length_for_siz[0] = 0;
	for (auto &[a, w] : graph[cent]) {
		if (marked[a])
			continue;
		update_k(a, cent, w, 1);
		update_mlfs(a, cent, w, 1);
	}
	reset_mlfs(cent, 0, 0);
	for (auto &[a, w] : graph[cent])
		if (!marked[a])
			dfs(a);
}

int best_path(int N, int K, int H[][2], int L[])
{
    n = N;
	k = K;
    graph.resize(n+1);
	marked.resize(n+1);
	sz.resize(n+1);
	min_len = 1e9;
	min_length_for_siz.resize(K+1, 1e9);
	for (int i = 0; i < n - 1; i++) {
		graph[H[i][0]].push_back(pair<int,int>(H[i][1], L[i]));
		graph[H[i][1]].push_back(pair<int,int>(H[i][0], L[i]));
	}
	dfs(1);
	if (min_len == 1e9)
    	return -1;
	return min_len;
}

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