Submission #1228722

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228722		felipe_massa	Race (IOI11_race)	C++20	100 / 100	710 ms	45020 KiB

race

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

constexpr int N = 2e5+5;
vector<pair<int, int>> adj[N];
int sz[N]; bool bl[N];
int ans = 1e9, k;

int dfs(int cur, int par) {
	sz[cur] = 1;
	for (auto p : adj[cur]) {
		int u = p.first, w = p.second;
		if (!bl[u] && u != par) 
			sz[cur] += dfs(u, cur);
	}
	return sz[cur];
}

int cent(int cur, int par, int tsz) {
	for (auto p : adj[cur]) if (p.first != par && !bl[p.first] &&
		tsz/2 < sz[p.first]) return cent(p.first, cur, tsz);
	return cur;
}

void dfs2(int cur, int par, int d, int nm, unordered_map<int, int>& aux) {
	if (aux.find(d) == aux.end()) {
		aux[d] = nm;
	} else {
		aux[d] = min(aux[d], nm);
	}
	for (auto p : adj[cur]) {
		int u = p.first, w = p.second;
		if (u != par && !bl[u]) {
			dfs2(u, cur, d + w, nm+1, aux);
		}
	}
}

void solve(int cur = 0) {
	int c = cent(cur, cur, dfs(cur, cur));
	bl[c] = true;
	unordered_map<int, int> cnt;
	cnt[0] = 0;
	for (auto p : adj[c]) {
		int u = p.first, w = p.second;
		if (!bl[u]) {
			unordered_map<int, int> aux;
			dfs2(u, c, w, 1, aux);
			for (auto x : aux) {
				if (cnt.find(k - x.first) != cnt.end())
					ans = min(ans, x.second + cnt[k - x.first]);
			}
			for (auto x : aux) {
				if (cnt.find(x.first) != cnt.end())
					cnt[x.first] = min(cnt[x.first], x.second);
				else cnt[x.first] = x.second;
			}
		}
	}
	for (auto p : adj[c]) if (!bl[p.first]) solve(p.first);
}

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]].push_back({H[i][1], L[i]});
		adj[H[i][1]].push_back({H[i][0], L[i]});
	}
	solve();
	return (ans >= 1e9 ? -1 : ans);
}

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