Submission #1309020

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309020		Nomio	Race (IOI11_race)	C++17	21 / 100	3093 ms	14464 KiB

race

#include<bits/stdc++.h>
#define ss second
#define ff first
#define pii pair<int, int> 
using namespace std;
using ll = long long;

const int maxn = 2e5 + 1;
const int maxk = 1e6 + 1;
vector<pii> adj[maxn];
vector<int> path(maxk, 1e9);
vector<pii> vec;
int sz[maxn] {};
bool removed[maxn] {};
int ans = 1e9, K;

int get_sz(int u, int p) {
	sz[u] = 1;
	for(pii P : adj[u]) {
		int v = P.ff;
		if(removed[v] || v == p) continue;
		sz[u] += get_sz(v, u);
	}
	return sz[u];
}

int get_centroid(int u, int p, int sze) {
	for(pii P : adj[u]) {
		int v = P.ff;
		int w = P.ss;
		if(removed[v] || v == p) continue;
		if(sz[v] > sze / 2) return get_centroid(v, u, sze);
	}
	return u;
}

void get_path(int u, int p, int dist, int depth) {
	if(dist > K) return;
	vec.push_back({dist, depth});
	for(pii P : adj[u]) {
		int v = P.ff;
		int w = P.ss;
		if(v == p || removed[v]) continue;
		get_path(v, u, dist + w, depth + 1);
	}
}

void solve(int u) {
	get_sz(u, -1);
	int center = get_centroid(u, -1, sz[u]);
	removed[center] = 1;
	fill(path.begin(), path.end(), 1e9);
	path[0] = 0;
	for(pii P : adj[center]) {
		int v = P.ff;
		int w = P.ss;
		if(removed[v]) continue;
		vec.clear();
		get_path(v, center, w, 1);
		for(pii P : vec) {
			int dist = P.ff;
			int depth = P.ss;
			ans = min(ans, depth + path[K - dist]);
		}
		for(pii P : vec) {
			int dist = P.ff;
			int depth = P.ss;
			path[dist] = min(path[dist], depth);
		}
	}
	for(pii P : adj[center]) {
		int v = P.ff;
		int w = P.ss;
		if(removed[v]) continue;
		solve(v);
	}
}

int best_path(int n, int k, int H[][2], int L[]) {
	K = k;
	for(int i = 0; i < n; i++) {
		adj[i].clear();
		removed[i] = 0;
	}
	ans = 1e9;
	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(0);
	return (ans == 1e9 ? -1 : ans);
}

//int main() {
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	int n, k;
//	cin >> n >> k;
//	int H[n][2], L[n];
//	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) << '\n';
//	return 0;
//}

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