제출 #1308974

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1308974		am_aadvik	경주 (Race) (IOI11_race)	C++20	100 / 100	1247 ms	64972 KiB

race

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<vector>
#include<map>
#define SUBMIT 1
const int inf = 2e9;
const int maxn = 2e5 + 5;
using namespace std;

vector<pair<int, int>> g[maxn];
int ans = inf, sub[maxn], found[maxn], n, k;
map<int, int> mp[maxn][2];
inline int cmin(int x, int y) { return min(x == 0 ? inf : x, y == 0 ? inf : y); }
void solve(int node, int par, int d, int dw, int c) {
	mp[c][0][dw] = cmin(mp[c][0][dw], d);
	if (dw == k) ans = min(ans, d);
	if (mp[c][1].find(k - dw) != mp[c][1].end()) ans = min(ans, mp[c][1][k - dw] + d);
	for (auto x : g[node])
		if ((x.first != par) && (!found[x.first]))
			solve(x.first, node, d + 1, dw + x.second, c);
}
int pre(int node, int par) {
	sub[node] = 1;
	for (const auto& x : g[node])
		if ((x.first != par) && (!found[x.first]))
			sub[node] += pre(x.first, node);
	return sub[node];
}
void shift(int c) { for (auto x : mp[c][0]) mp[c][1][x.first] = cmin(mp[c][1][x.first], x.second); }
bool dfs(int node, int par, int cn) {
	for (const auto& x : g[node])
		if (((x.first == par ? -cn : sub[x.first]) > (cn / 2)) && !found[x.first])
			return dfs(x.first, node, cn);
	found[node] = 1; pre(node, 0);
	for (auto x : g[node])
		if (!found[x.first])
			solve(x.first, node, 1, x.second, node),
			shift(node), mp[node][0].clear(),
			dfs(x.first, node, sub[x.first]);
	mp[node][1].clear(); return 1;
}
int32_t best_path(int32_t N, int32_t K, int32_t h[][2], int32_t l[]) {
	n = N, k = K;
	for (int i = 0; i < (n - 1); ++i)
		g[h[i][0] + 1].push_back({ h[i][1] + 1, l[i] }),
		g[h[i][1] + 1].push_back({ h[i][0] + 1, l[i] });
	pre(1, 0); dfs(1, 0, n);
	return (int32_t)(ans == inf ? -1 : ans);
}

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