Submission #599879

#	Time	Username	Problem	Language	Result	Execution time	Memory
599879		acatmeowmeow	Race (IOI11_race)	C++11	43 / 100	285 ms	28648 KiB

race

#include "race.h"

#include <bits/stdc++.h>

using namespace std;

//#define int long long 

const int NMAX = 2e5 + 5;

vector<pair<int, int>> adj[NMAX];

int sz[NMAX];
bool removed[NMAX];

int get_size(int u, int e) {
	sz[u] = 1;
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || removed[v]) continue;
		sz[u] += get_size(v, u);
	}
	return sz[u];
}

int get_centroid(int u, int e, int s) {
	for (auto&x : adj[u]) {
		int v = x.first;
		if (v == e || removed[v] || 2*sz[v] <= s) continue;
		return get_centroid(v, u, s);
	}
	return u;
}

int dist[NMAX], depth[NMAX], ans = 1e6;

void dfs(int u, int e, int K, map<int, int>&edge) {
	if (dist[u] > K) return;
	if (dist[u] == K) ans = min(ans, depth[u]);
	else if (edge.count(K - dist[u])) ans = min(ans, depth[u] + edge[K - dist[u]]);
	for (auto&x : adj[u]) {
		int v = x.first, c = x.second;
		if (v == e || removed[v]) continue;
		dist[v] = dist[u] + c, depth[v] = depth[u] + 1;
		dfs(v, u, K, edge);
	}
	if (!edge.count(dist[u])) edge[dist[u]] = depth[u];
	edge[dist[u]] = min(edge[dist[u]], depth[u]);
}

void build(int u, int e, int K) {
	int s = get_size(u, e), centroid = get_centroid(u, e, s);
	map<int, int> edge;
	dist[centroid] = depth[centroid] = 0;
	dfs(centroid, -1, K, edge);
	removed[centroid] = true;
	for (auto&x : adj[centroid]) {
		int v = x.first;
		if (v == e || removed[v]) continue;
		build(v, centroid, K);
	}
}

signed best_path(signed N, signed K, signed H[][2], signed L[]) {
	for (int i = 0; i < N - 1; i++) {
		int u = H[i][0], v = H[i][1], c = L[i];
		adj[u].push_back({v, c}), adj[v].push_back({u, c});
	}
	build(0, -1, K);
	return ans == 1e6 ? -1 : ans;
}

/*signed N, K, H[NMAX][2], L[NMAX];

signed main() {
	cin >> N >> K;
	for (int i = 0; i < N - 1; i++) cin >> H[i][0] >> H[i][1] >> L[i];
	cout << best_path(N, K, H, L) << '\n'; 
	return 0;
}*/

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