Submission #1222477

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222477		Bui_Quoc_Cuong	Race (IOI11_race)	C++20	100 / 100	970 ms	34112 KiB

race

/* 29 . 03. 2008 */
# include <bits/stdc++.h>
using namespace std ;

const int N = 2e5 + 5 ;
const int M = 1e6 + 5 ; 
const long long inf = 1e18 ;

int n, k ;
vector <pair<int,int>> g[N] ;
int is_centroid[N], sz[N] ;
int cnt[M] ;
int ans ;

void dfs(int u, int p) {
	sz[u] = 1 ;
	for(pair<int, int> x : g[u]) {
		int v = x.first ; 
		if(v == p || is_centroid[v]) continue ;
		dfs(v, u) ; 
		sz[u]+= sz[v] ;
	}
}

int findCentroid(int u, int p, int big) {
	for(pair<int, int> x : g[u]) {
		int v = x.first ; 
		if(v == p || is_centroid[v]) continue ; 
		if(sz[v] > big / 2) return findCentroid(v, u, big) ; 
	}
	return u ; 
}

int max_depth ;

void updateAns(int u, int p, int t, int d, int w) {
	if(w > k) return ; 

	if(t == 1) cnt[w] = min(cnt[w], d) ; 
	else ans = min(ans, cnt[k - w] + d) ;

	max_depth = max(max_depth, w) ;

	for(pair<int, int> x : g[u]) {
		int v = x.first , len = x.second ;
		if(v == p || is_centroid[v]) continue ; 
		updateAns(v, u, t, d + 1, w + len) ;
	} 
}

void buildCentroid(int u) {
	dfs(u, - 1) ; 
	int centroid = findCentroid(u, - 1, sz[u]) ; 
	is_centroid[centroid] = 1 ; 

	max_depth = 0 ;

	for(pair<int, int> x : g[centroid]) {
		int v = x.first , w = x.second ;
		if(is_centroid[v]) continue ; 
		updateAns(v, centroid, 0, 1, w) ; 
		updateAns(v, centroid, 1, 1, w) ;
	}

	for(int i = 1; i <= max_depth; i++) cnt[i] = 2e9 ;

	for(pair<int, int> x : g[centroid]) {
		int v = x.first ; 
		if(!is_centroid[v]) buildCentroid(v) ; 
	}
}

void solve() {
	for(int i = 0; i <= k; i++) cnt[i] = 2e9 ;
	ans = 2e9 ;
	cnt[0] = 0 ;
	buildCentroid(1) ;
	cout << (ans >= 2e9 ? - 1 : ans) ;
}

array <int, 2> E[N];

int best_path(int _n, int _k, int h[][2], int l[]){
	n = _n;
	k = _k;
	for(int i = 0; i < n; i++){
		h[i][0]++; h[i][1]++;
		g[h[i][0]].emplace_back(h[i][1], l[i]);
        g[h[i][1]].emplace_back(h[i][0], l[i]);
	}
	for(int i = 0; i <= k; i++) cnt[i] = 2e9;
	ans = 2e9 ;
	cnt[0] = 0 ;
	buildCentroid(1) ;
	return (ans >= 2e9 ? - 1 : ans);
}

// signed main() {
// 	#define task "race"
// 	ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ;
// 	// if(fopen(task".inp", "r")) {
// 	// 	freopen(task".inp","r",stdin) ; freopen(task".out","w",stdout) ;
// 	// }
// 	// if(fopen(".inp","r")) {
// 	// 	freopen(".inp","r",stdin) ; freopen(".out","w",stdout) ;
// 	// }
// 	cin >> n >> k ; 
// 	for(int i = 1; i < n; i++) {
// 		int u, v, w ; cin >> u >> v;
// 		u++, v++ ; 
// 		E[i] = {u, v};
// 		// g[u].emplace_back(make_pair(v, w)) ; g[v].emplace_back(make_pair(u, w)) ;
// 	}
// 	for(int i = 1; i < n; i++){
// 		int w; cin >> w;
// 		int u = E[i][0], v = E[i][1];
// 		g[u].emplace_back(make_pair(v, w)) ; g[v].emplace_back(make_pair(u, w)) ;
// 	}
// 	solve() ; 
// 	cerr << "\nTime :" << 0.001 * clock() << "s " ; 
// 	return 0 ;
// }
/* Watbor */

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