Submission #759234

#	Time	Username	Problem	Language	Result	Execution time	Memory
759234		raysh07	Race (IOI11_race)	C++17	100 / 100	695 ms	42572 KiB

race

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

const int maxn = 2e5 + 69;
int n, k;
vector <pair<int, int>> adj[maxn];
bool del[maxn];
int sz[maxn];
map <int, int> mp;
vector <int> comp;
int ans = 1e9;
vector <pair<int, int>> vec;

void dfs(int u, int par, int dist, int dep = 1){
	if (dist > k) return;
	vec.push_back(make_pair(dist, dep));
	if (mp.find(k - dist) != mp.end()){
		ans = min(ans, mp[k - dist] + dep);
	}

	for (auto [v, w] : adj[u]){
		if (!del[v] && v != par){
			dfs(v, u, dist + w, dep + 1);
		}
	}
}

void dfs2(int u, int par){
	sz[u] = 1;
	comp.push_back(u);
	for (auto [v, w] : adj[u]){
		if (!del[v] && v != par){
			dfs2(v, u);
			sz[u] += sz[v];
		}
	}
}

int find(int x){
	comp.clear();
	dfs2(x, -1);

	for (auto u : comp){
		int mx = 0;
		for (auto [v, w] : adj[u]){
		    if (!del[v] && sz[v] < sz[u])
			mx = max(mx, sz[v]);
		}
		mx = max(mx, (int)comp.size() - 1 - sz[u]);
		
// 		cout << u << " " << mx << "\n";
		if (2 * mx <= (int)comp.size()) return u;
	}
	
// 	for (auto x : comp){
// 	    cout << x << " " << sz[x] << "\n";
// 	}
// 	exit(0);

	assert(false);
}

void cd(int x){
	x = find(x);
	mp.clear();

	mp[0] = 0;
	int u = x;
	for (auto [v, w] : adj[u]){
		if (!del[v]){
			dfs(v, u, w);
			for (auto [x, y] : vec){
				if (mp.find(x) == mp.end()) mp[x] = y;
				else mp[x] = min(mp[x], y);
			}
			vec.clear();
		}
	}

	del[x] = true;
	for (auto [v, w] : adj[x]){
		if (!del[v]){
			cd(v);
		}
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	n = N; k = K;
	for (int i = 0; i < n - 1; i++){
		int u = H[i][0];
		int v = H[i][1];
		int w = L[i];

		adj[u].push_back(make_pair(v, w));
		adj[v].push_back(make_pair(u, w));
	}

	cd(0);

	if (ans == 1e9) return -1;
	else return ans;
}

// int main(){
// 	int n, k; cin >> n >> k;

// 	int H[n - 1][2], L[n - 1];
// 	for (int i = 0; i < n - 1; i++){
// 		cin >> H[i][0] >> H[i][1];
// 	}
// 	for (int i = 0; i < n - 1; i++) cin >> L[i];

// 	cout << best_path(n, k, H, L);
// 	return 0;
// }

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