Submission #302327

#	Time	Username	Problem	Language	Result	Execution time	Memory
302327		nhdtxdy	Race (IOI11_race)	C++17	100 / 100	528 ms	73520 KiB

race

#include <bits/stdc++.h>
#define eb emplace_back
#define Size(v) (int)v.size()
using namespace std;

// Always
const int nax = 2e5 + 5, INF = 1e9 + 7;
int n, k;
vector<pair<int, int>> adj[nax];
unordered_map<int, int> vec[nax];
int dist[nax], ans[nax], sz[nax], dep[nax];

void getsz(int v, int p = 0) {
	sz[v] = 1;
	for (auto &q : adj[v]) {
		int c = q.first, w = q.second;
		if (c == p) continue;
		dep[c] = dep[v] + 1;
		dist[c] = dist[v] + w;
		getsz(c, v);
		sz[v] += sz[c];
	}
}

void dfs(int v, int p = 0, bool keep = false) {
	int maxi = -1, bigchild = -1;
	for (auto &q : adj[v]) {
		int u = q.first;
		if (u == p) continue;
		if (maxi < sz[u]) {
			maxi = sz[u];
			bigchild = u;
		}
	}
	for (auto &q : adj[v]) {
		int u = q.first;
		if (u == p || u == bigchild) continue;
		dfs(u, v, false);
	}
	if (bigchild != -1) {
		dfs(bigchild, v, true);
		swap(vec[v], vec[bigchild]);
	}
	vec[v][dist[v]] = dep[v];	
	int subtract = dist[v];
	if (vec[v].find(k + dist[v]) != vec[v].end()) {
		ans[v] = min(ans[v], vec[v][k + dist[v]] - dep[v]);
	}
	int target = k + 2 * subtract;
	for (auto &q : adj[v]) {
		int c = q.first;
		if (c == p || c == bigchild) continue;
		if (vec[c].find(k + dist[v]) != vec[c].end()) {
			ans[v] = min(ans[v], vec[c][k + dist[v]] - dep[v]);
		}
		for (auto &u : vec[c]) {
			if (vec[v].find(target - u.first) != vec[v].end()) {
				ans[v] = min(ans[v], u.second + vec[v][target - u.first] - 2 * dep[v]);
			}
		}
		for (auto &u : vec[c]) {
			if (vec[v].find(u.first) != vec[v].end()) vec[v][u.first] = min(vec[v][u.first], u.second);
			else vec[v][u.first] = u.second;
		}
	}
}

int best_path(int N, int K, int H[][2], int L[]) {
	fill(ans, ans + nax, INF);
	n = N;
	k = K;
	for (int i = 0; i < n - 1; ++i) {
		int u = H[i][0], v = H[i][1];
		++u, ++v;
		adj[u].eb(v, L[i]);
		adj[v].eb(u, L[i]);
	}
	getsz(1);
	dfs(1);
	int res = INF;
	for (int i = 1; i <= n; ++i) res = min(res, ans[i]);
	if (res == INF) return -1;
	return res;
}

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