Submission #551201

#	Time	Username	Problem	Language	Result	Execution time	Memory
551201		Sohsoh84	Race (IOI11_race)	C++17	100 / 100	920 ms	63352 KiB

race

#include "race.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

#define X			first
#define Y			second
#define sep			' '
#define debug(x)		cerr << #x << ": " << x << endl;

const ll INF = 1e9;
const ll MAXN = 1e6 + 10;

int n, k, ans, sz[MAXN];
vector<pll> adj[MAXN];
bool B[MAXN];
map<ll, int> mp;
vector<pll> vec;

int sub_sz(int v, int p) {
	sz[v] = 1;
	for (auto [u, w] : adj[v])
		if (!B[u] && u != p)
			sz[v] += sub_sz(u, v);
	return sz[v];
}

int centroid(int v, int p, int n) {
	for (auto [u, w] : adj[v])
		if (!B[u] && u != p && sz[u] * 2 > n)
			return centroid(u, v, n);
	return v;
}

void dfs(int v, int p, ll w, int l) {
	vec.push_back({w, l});
	auto it = mp.find(k - w);
	if (it != mp.end()) ans = min(ans, l + it -> Y);

	for (auto [u, e_w] : adj[v])
		if (u != p && !B[u])
			dfs(u, v, w + e_w, l + 1);
}

void solve(int v) { 
	B[v = centroid(v, 0, sub_sz(v, 0))] = true;
	mp.clear();
	mp[0] = 0;

	for (auto [u, w] : adj[v]) {
		if (!B[u]) {
			dfs(u, v, w, 1);
			for (pll e : vec) {
				auto it = mp.find(e.X);
				if (it == mp.end() || it -> Y > e.Y)
					mp[e.X] = e.Y;
			}

			vec.clear();
		}
	}

	for (auto [u, w] : adj[v])
		if (!B[u])
			solve(u);
}

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], l = L[i];
		u++, v++;
		adj[u].push_back({v, l});
		adj[v].push_back({u, l});
	}

	ans = INF;
	solve(1);
	return (ans == INF ? -1 : ans);
}

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