Submission #349765

#	Time	Username	Problem	Language	Result	Execution time	Memory
349765		pavement	Race (IOI11_race)	C++17	100 / 100	524 ms	146028 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
int _K, ans = 1e9, dist[1000005], dep[1000005];
vector<pair<int, int> > adj[1000005];
set<pair<int, int> > S[1000005];
 
void dfs(int n, int e = -1) {
	S[n].emplace(dist[n], dep[n]);
	for (auto u : adj[n]) {
		if (u.first != e) {
			dist[u.first] = dist[n] + u.second;
			dep[u.first] = dep[n] + 1;
			dfs(u.first, n);
			if (S[n].size() < S[u.first].size()) swap(S[n], S[u.first]);
			for (auto i : S[u.first]) {
				auto it = S[n].lower_bound(make_pair(_K - i.first + 2 * dist[n], 0));
				if (it != S[n].end() && it->first + i.first - 2 * dist[n] == _K) ans = min(ans, it->second + i.second - 2 * dep[n]);
			}
			for (auto i : S[u.first]) S[n].insert(i);
		}
	}
}
 
int best_path(int N, int K, int H[][2], int L[]) {
	_K = K;
	for (int i = 0; i < N - 1; i++) {
		adj[H[i][0]].emplace_back(H[i][1], L[i]);
		adj[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	dfs(0);
	return (ans == 1e9 ? -1 : ans);
}

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