제출 #600238

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
600238		acatmeowmeow	경주 (Race) (IOI11_race)	C++11	100 / 100	1533 ms	60748 KiB

race

#include "race.h"
//#include "grader.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] || sz[v] <= s/2) continue;
		return get_centroid(v, u, s);
	}
	return u;
}

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

void dfs(int u, int e, int root, map<int, int>&res) {
	if (!res.count(dist[u])) res[dist[u]] = depth[u];
	res[dist[u]] = min(res[dist[u]], depth[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, root, res);
	}
}

void build(int u, int e, int K, int N) {
	int s = get_size(u, e), centroid = get_centroid(u, e, s);
	//
	map<int, int> tot;
	tot[0] = dist[centroid] = depth[centroid] = 0;
	for (auto&x : adj[centroid]) {
		int v = x.first, c = x.second;
		if (v == e || removed[v]) continue;
		dist[v] = dist[centroid] + c, depth[v] = depth[centroid] + 1;
		map<int, int> res;
		dfs(v, centroid, v, res);
		if (tot.size() < res.size()) swap(tot, res);
		for (auto&x : res) {
			int cost = x.first, edge = x.second;
			if (tot.count(K - cost)) ans = min(ans, edge + tot[K - cost]);
		}
		for (auto&x : res) {
			int cost = x.first, edge = x.second;
			if (tot.count(cost)) tot[cost] = min(tot[cost], edge);
			else tot[cost] = edge;
		}
	}
	// 	
	removed[centroid] = true;
	for (auto&x : adj[centroid]) {
		int v = x.first;
		if (v == e || removed[v]) continue;
		build(v, centroid, K, N);
	}
}

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});
		adj[u].push_back(make_pair(v, c)), adj[v].push_back(make_pair(u, c));
	}
	build(0, -1, K, N);
	return ans == 1e18 ? -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: 57 / 57