Submission #1113010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1113010		akzytr	Race (IOI11_race)	C++17	43 / 100	3073 ms	96584 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define ve vector
#define pb push_back
#define ar array
#define ll long long
using namespace std;

const int MAXN = 3e5;
const int MAXK = 2e6 + 1;
set<int> adj[MAXN];
map<ar<int, 2>, int> w;

int K;
int ANS = 1e9;

int BOOK = 1;

int sub[MAXN];
int A[MAXK];
int BOOK_K[MAXK];

void find_size(int x, int p) {
	sub[x] = 1;
	for(int i : adj[x]) {
		if(i != p) {
			find_size(i, x);
			sub[x] += sub[i];
		}
	}
}
int find_centroid(int x, int p, int n) {
	for(int i : adj[x]) {
		if(sub[i] > n / 2 && i != p) {
			return find_centroid(i, x, n);
		}
	}
	return x;
}

void dfs(int x, int p, int we, int num_edge, bool upd) {
	if(we > K) {
		return;
	}
	if(upd) {
		if(BOOK_K[we] != BOOK) {
			BOOK_K[we] = BOOK;
			A[we] = num_edge;
		} else {
			A[we] = min(A[we], num_edge);
		}
	} else {
		if(BOOK_K[K - we] == BOOK) {
			ANS = min(ANS, num_edge + A[K - we]);
		}
	}

	for(int i : adj[x]) {
		if(i != p && we + w[{i, x}] <= K) {
			dfs(i, x, we + w[{i, x}], num_edge + 1, upd);
		}
	}
}
void process_centroid(int x) {
	BOOK++;
	A[0] = 0;
	BOOK_K[0] = BOOK;

	for(int i : adj[x]) {
		dfs(i, x, w[{i, x}], 1, false);
		dfs(i, x, w[{i, x}], 1, true);
	}
}

void decompo(int x, int p) {
	find_size(x, p);
	int centroid = find_centroid(x, p, sub[x]);
	process_centroid(centroid);

	for(int i : adj[centroid]) {
		adj[i].erase(centroid);
		decompo(i, x);
	}
}

int best_path(int N, int Ked, int H[][2], int L[]) {
	fill(A, A + MAXK, 0);
	fill(BOOK_K, BOOK_K + MAXK, 0);
	for(int i = 0; i < N - 1; i++) {
		int a, b;
		a = H[i][0];
		b = H[i][1];

		adj[a].insert(b);
		adj[b].insert(a);
		w[{a, b}] = L[i];
		w[{b, a}] = L[i];
	}
	K = Ked;
	decompo(0, -1);
	if(ANS != 1e9) {
		return ANS;
	}
	return -1;
}

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