제출 #1308971

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

race

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

///////////////////////////////////////////////////////////////////////////
//main code
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][k - dw]) 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]);
	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);
}
///////////////////////////////////////////////////////////////////////////

#if SUBMIT == 0
#define MAX_N 500000
static int32_t N, K;
static int32_t H[MAX_N][2];
static int32_t L[MAX_N];
static int32_t solution;

inline void my_assert(int e) { if (!e) abort(); }
void read_input() {
	int i;
	my_assert(2 == scanf("%d %d", &N, &K));
	for (i = 0; i < N - 1; i++)
		my_assert(3 == scanf("%d %d %d", &H[i][0], &H[i][1], &L[i]));
	my_assert(1 == scanf("%d", &solution));
}
int32_t main() {
	int ans;
	read_input();
	ans = best_path(N, K, H, L);
	if (ans == solution)
		printf("Correct.\n");
	else
		printf("Incorrect. Returned %d, Expected %d.\n", ans, solution);

	return 0;
}
#endif

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