Submission #385587

#	Time	Username	Problem	Language	Result	Execution time	Memory
385587		negar_a	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

//!yrt tsuj uoy srettam gnihton no emoc
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
#define pb push_back
#define mp make_pair
#define pii pair <int, int>
#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define F first
#define S second

const int maxn = 1e5 + 5, N = 1e6 + 5;
vector <pii> adj[maxn];
ll w[maxn], sz[maxn];
ll h[maxn], d[maxn], mn[N];
ll n, k;
ll inf = INT_MAX, ans = INT_MAX;
bool dead[maxn];

void dfs(int v, int p = -1){
	sz[v] = 1;
	for(auto u : adj[v]){
		if(u.F != p && !dead[u.F]){
			d[u.F] = d[v] + w[u.S];
			h[u.F] = h[v] + 1;
			dfs(u.F, v);
			sz[v] += sz[u.F]; 
		}
	}
}
int find_centroid(int v, int p, int z){
	for(auto u : adj[v]){
		if(u.F != p && !dead[u.F] && sz[u.F] > z / 2){
			return find_centroid(u.F, v, z);
		}
	}
	return v;
}

void get(int v, int p = -1){
	if(k - d[v] >= 0){
		ans = min(mn[k - d[v]] + h[v], ans);
	}
	for(auto u : adj[v]){
		if(u.F != p && !dead[u.F]){
			get(u.F, v);
		}
	}
}
void upd(int v, int p = -1){
	if(k - d[v] >= 0){
		mn[d[v]] = min(h[v], mn[d[v]]);
	}
	for(auto u : adj[v]){
		if(u.F != p && !dead[u.F]){
			upd(u.F, v);
		}
	}
}
void clr(int v, int p = -1){
	mn[d[v]] = inf;
	for(auto u : adj[v]){
		if(u.F != p && !dead[u.F]){
			upd(u.F, v);
		}
	}
}

void solve(int v){
	dfs(0);
	int c = find_centroid(v, -1, sz[v]);
	dead[c] = true;
	h[c] = d[c] = 0;
	dfs(c);
	for(auto x : adj[c]){
		int u = x.F;
		if(!dead[u]){
			get(u, c);
			upd(u, c);
		}
	}
	ans = min(ans, mn[k]);
	clr(c);
	for(auto x : adj[c]){
		if(!dead[x.F]){
			solve(x.F);
		}
	}
}

int main(){
	fast_io;
	
	cin >> n >> k;
	for(int i = 0; i < n - 1; i ++){
		int x, y;
		cin >> x >> y;
		adj[x].pb({y, i});
		adj[y].pb({x, i});
	}
	for(int i = 0; i < n - 1; i ++){
		cin >> w[i];
	}
	for(int i = 0; i < N - 2; i ++){
		mn[i] = inf;
	}
	solve(0);
	if(ans >= inf){
		cout << -1;
	}
	else{
		cout << ans;
	}
	return 0;
}
/*
11 12
0 1
0 2
2 3
3 4
4 5
0 6
6 7
6 8
8 9
8 10
3
4
5
4
6
3
2
5
6
7
-----------
4 3
0 1
1 2
1 3
1
2
4
----------
3 3
0 1
1 2
1 
1
*/

Compilation message (stderr)

/tmp/cc5bXIEh.o: In function `main':
race.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccNXgPoS.o:grader.cpp:(.text.startup+0x0): first defined here
/tmp/ccNXgPoS.o: In function `main':
grader.cpp:(.text.startup+0x24): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status