Submission #933192

#	Time	Username	Problem	Language	Result	Execution time	Memory
933192		SmuggingSpun	Race (IOI11_race)	C++17	9 / 100	304 ms	43348 KiB

race

#include "race.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>void minimize(T& a, T b){
	if(a > b){
		a = b;
	}
}
const int lim = 2e5 + 5;
const int LIM = 1e6 + 1;
const int INF = 1e9;
vector<pair<int, int>>e[lim];
vector<int>g[lim];
int n, k, ans = INT_MAX, h[lim], up[lim][18], cnt[lim], value[LIM];
bitset<lim>in_centroid;
ll f[lim];
void dfs(int s, int p = -1){
	cnt[s] = 1;
	for(auto& [d, w] : e[s]){
		if(d != p){
			f[d] = f[up[d][0] = s] + w;
			h[d] = h[s] + 1;
			for(int i = 1; i < 18; i++){
				up[d][i] = up[up[d][i - 1]][i - 1];
			}
			dfs(d, s);
		}
	}
}
int lca(int u, int v){
	if(h[u] < h[v]){
		swap(u, v);
	}
	int k = h[u] - h[v];
	while(k > 0){
		int x = __builtin_ctz(k);
		u = up[u][x];
		k ^= 1 << x;
	}
	if(u == v){
		return u;
	}
	for(int i = 17; i > -1; i--){
		int U = up[u][i], V = up[v][i];
		if(U != V){
			u = U;
			v = V;
		}
	}
	return u;
}
ll get_distance(int u, int v){
	return f[u]  + f[v] - (f[lca(u, v)] << 1);
}
int get_distance_height(int u, int v){
	return h[u] + h[v] - (h[lca(u, v)] << 1);
}
void build_cnt(int s, int p = -1){
	cnt[s] = 1;
	for(auto& [d, w] : e[s]){
		if(d != p && !in_centroid.test(d)){
			build_cnt(d, s);
			cnt[s] += cnt[d];
		}
	}
}
int get_centroid(int s, int n, int p = -1){
	for(auto& [d, w] : e[s]){
		if(d != p && !in_centroid.test(d) && cnt[d] > (n >> 1)){
			return get_centroid(d, n, s);
		}
	}
	return s;
} 
int centroid_decomposition(int s, int p = -1){
	build_cnt(s, p);
	int centroid = get_centroid(s, cnt[s], p);
	in_centroid.set(centroid);
	for(auto& [d, w] : e[centroid]){
		if(!in_centroid.test(d)){
			g[centroid].emplace_back(centroid_decomposition(d, centroid));
		}
	}
	return centroid;
}
vector<int>vertex;
void dfs_centroid_support(int root, int s, bool is_add){
	ll D = get_distance(root, s);
	if(D <= k){
		if(is_add){
			vertex.emplace_back(s);
		}
		else{
			value[D] = INF;
		}
	}
	for(int& d : g[s]){
		dfs_centroid_support(root, d, is_add);
	}
}
void dfs_centroid(int s){
	value[0] = 0;
	for(int& d : g[s]){
		vertex.clear();
		dfs_centroid_support(s, d, true);
		for(int& x : vertex){
			minimize(ans, get_distance_height(s, x) + value[k - get_distance(s, x)]);
		}
		for(int& x : vertex){
			minimize(value[get_distance(s, x)], get_distance_height(s, x)); 
		}
	}
	dfs_centroid_support(s, s, false);
	for(int& d : g[s]){
		dfs_centroid(d);
	}
}
int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	for(int i = 0; i < n; i++){
		e[H[i][0]].emplace_back(H[i][1], L[i]);
		e[H[i][1]].emplace_back(H[i][0], L[i]);
	}
	memset(up, h[0] = f[0] = 0, sizeof(up));
	dfs(0);
	in_centroid.reset();
	memset(value, 0x0f, sizeof(value));
	dfs_centroid(centroid_decomposition(0));
	return ans > n ? -1 : ans;
}

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