Submission #456362

#	Time	Username	Problem	Language	Result	Execution time	Memory
456362		TruaShamu	Race (IOI11_race)	C++17	100 / 100	634 ms	34000 KiB

race

#include <bits/stdc++.h>
using namespace std;

#define MAXN 200005
#define ii pair<int, int>
#define ll long long

int N, K, ans, cnt[1000100], subSize[MAXN], root[MAXN];
vector<ii> adj[MAXN];
inline void minimize(int& a, int b) {
	if (a == -1 || a > b) {
		a = b;
	}
}


void get_cnt(int sum, bool filling, int cur, int par = -1, int depth = 1) {
	if (sum > K) {
		return;
	}
	if (filling) {
		minimize(cnt[sum], depth);
	}
	else {
		if (cnt[K - sum] != -1) {
			minimize(ans, depth + cnt[K - sum]);
		}
	}
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (next != par && !root[next]) {
			get_cnt(sum + cost, filling, next, cur, depth + 1);
		}
	}
}

void del(int sum, int cur, int par = -1) {
	if (sum > K) return;
	cnt[sum] = -1;
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (next != par && !root[next]) {
			del(sum + cost, next, cur);
		}
	}
}


// Find subtree size under each node.
int dfs(int cur, int par = -1) {
	subSize[cur] = 1;
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (next != par && !root[next]) {
			subSize[cur] += dfs(next, cur);
		}
	}
	return subSize[cur];
}


// Get the centroid within the subtree.
int get_centroid(int size, int cur, int par = -1) {
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		if (next != par && !root[next] && 2 * subSize[next] > size) {
			return get_centroid(size, next, cur);
		}
	}
	return cur;
}


void centroid(int cur = 0) {
	cur = get_centroid(dfs(cur), cur);
	root[cur] = 1;
	cnt[0] = 0;
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (!root[next]) {
			get_cnt(cost, false, next);
			get_cnt(cost, true, next);
		}
	}

	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		int cost = oPair.second;
		if (!root[next]) {
			del(cost, next);
		}
	}
	for (auto& oPair : adj[cur]) {
		int next = oPair.first;
		if (!root[next]) {
			centroid(next);
		}
	}
}


int best_path(int n, int k, int H[][2], int L[]) {
	N = n;
	K = k;
	for (int i = 0, u, v; i < N - 1; i++) {
		u = H[i][0];
		v = H[i][1];
		adj[u].push_back(ii(v, L[i]));
		adj[v].push_back(ii(u, L[i]));

	}
	ans = -1;
	memset(cnt, -1, sizeof(cnt));
	centroid();
	return ans;
}

Compilation message (stderr)

race.cpp: In function 'int dfs(int, int)':
race.cpp:56:7: warning: unused variable 'cost' [-Wunused-variable]
   56 |   int cost = oPair.second;
      |       ^~~~

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