Submission #1222474

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222474		Bui_Quoc_Cuong	Race (IOI11_race)	C++20	Compilation error	0 ms	0 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];

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 */

Compilation message (stderr)

/usr/bin/ld: /tmp/ccqKZs5J.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccnt61YA.o:race.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccqKZs5J.o: in function `main':
grader.cpp:(.text.startup+0x28): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status