Submission #507490

#	Time	Username	Problem	Language	Result	Execution time	Memory
507490		haxorman	Race (IOI11_race)	C++14	100 / 100	437 ms	35844 KiB

race

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

const int mxN = 2e5 + 7;
const int mxK = 1e6 + 7;

int n, k;
vector<int> cur_seg;
vector<pair<int,int>> sums, graph[mxN];
int dp[mxN], p[mxN], len[mxK];
bool vis[mxN];

void dfs(int u, int par) {
	dp[u] = 1;
	p[u] = par;

	for (auto pr : graph[u]) {
		int v = pr.first;
		if (!vis[v] && v != par) {
			dfs(v, u);
			dp[u] += dp[v];
		}
	}

	cur_seg.push_back(u);
}

int find_centroid(int x) {
	cur_seg.clear();
	dfs(x, -1);

	for (int u : cur_seg) {
		int max_subtree = cur_seg.size() - dp[u];

		for (auto pr : graph[u]) {
			int v = pr.first;
			if (v != p[u] && !vis[v]) {
				max_subtree = max(max_subtree, dp[v]);
			}
		}

		if (max_subtree <= cur_seg.size() / 2) {
			return u;
		}
	}

	return x;
}

int ans = INT_MAX;

void find_min_path(int u, int par, int cnt, int sum) {
	if (sum < k && len[k - sum]) {
		ans = min(ans, cnt + len[k - sum]);
	}
	else if (sum == k) {
		ans = min(ans, cnt);
	}
	
	if (sum > k) {
		return;
	}

	for (auto pr : graph[u]) {
		int v = pr.first, w = pr.second;
		if (!vis[v] && v != par) {
			find_min_path(v, u, cnt + 1, sum + w);
		}
	}

	sums.push_back({sum, cnt});
}

void decompose(int x) {
	int c = find_centroid(x);
	vis[c] = true;
	
	vector<int> reset;

	for (auto pr : graph[c]) {
		int v = pr.first, w = pr.second;
		if (!vis[v]) {
			sums.clear();
			find_min_path(v, c, 1, w);

			for (auto prr : sums) {
				int sum = prr.first, cnt = prr.second;
				if (!len[sum]) {
					len[sum] = cnt;
				}
				else {
					len[sum] = min(len[sum], cnt);
				}
				reset.push_back(sum);
			}
		}
	}

	for (auto sum : reset) {
		len[sum] = 0;
	}

	for (auto pr : graph[c]) {
		int v = pr.first;
		if (!vis[v]) {
			decompose(v);
		}
	}
}

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

		graph[u].push_back({v, w});
		graph[v].push_back({u, w});
	}

	decompose(0);
	return (ans == INT_MAX ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'int find_centroid(int)':
race.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |   if (max_subtree <= cur_seg.size() / 2) {
      |       ~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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