Submission #760622

#	Time	Username	Problem	Language	Result	Execution time	Memory
760622		SanguineChameleon	Race (IOI11_race)	C++17	100 / 100	391 ms	36396 KiB

race

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

const int maxN = 2e5 + 20;
const int maxK = 1e6 + 20;
vector<pair<int, int>> adj[maxN];
bool flag[maxN];
int sz[maxN];
int best[maxK];
pair<int, int> dist[maxN];
int res;
int N, K;

void dfs1(int u, int p) {
	sz[u] = 1;
	for (auto e: adj[u]) {
		int v = e.first;
		if (!flag[v] && v != p) {
			dfs1(v, u);
			sz[u] += sz[v];
		}
	}
}

int cen(int r, int u, int p) {
	for (auto e: adj[u]) {
		int v = e.first;
		if (!flag[v] && v != p && sz[v] * 2 > sz[r]) {
			return cen(r, v, u);
		}
	}
	return u;
}

void dfs2(int u, int p, int op) {
	if (dist[u].second > K) {
		return;
	}
	if (op == 1) {
		res = min(res, dist[u].first + best[K - dist[u].second]);
	}
	if (op == 2) {
		best[dist[u].second] = min(best[dist[u].second], dist[u].first);
	}
	if (op == 3) {
		best[dist[u].second] = N;
	}
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (!flag[v] && v != p) {
			dist[v] = make_pair(dist[u].first + 1, dist[u].second + w);
			dfs2(v, u, op);
		}
	}
}

void solve(int u) {
	dfs1(u, -1);
	u = cen(u, u, -1);
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (!flag[v]) {
			dist[v] = make_pair(1, w);
			dfs2(v, u, 1);
			dfs2(v, u, 2);
		}
	}
	for (auto e: adj[u]) {
		int v = e.first;
		int w = e.second;
		if (!flag[v]) {
			dist[v] = make_pair(1, w);
			dfs2(v, u, 3);
		}
	}
	flag[u] = true;
	for (auto e: adj[u]) {
		int v = e.first;
		if (!flag[v]) {
			solve(v);
		}
	}
}

int best_path(int _N, int _K, int H[][2], int L[]) {
	N = _N;
	K = _K;
	best[0] = 0;
	for (int i = 1; i <= K; i++) {
		best[i] = N;
	}
	res = N;
	for (int i = 0; i < N - 1; i++) {
		int u = H[i][0];
		int v = H[i][1];
		int w = L[i];
		adj[u].emplace_back(v, w);
		adj[v].emplace_back(u, w);
	}
	solve(1);
	if (res == N) {
		return -1;
	}
	else {
		return res;
	}
}

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