제출 #385830

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
385830		negar_a	경주 (Race) (IOI11_race)	C++14	43 / 100	669 ms	45276 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 ll maxn = 2e5 + 5, maxk = 1e6 + 5;
vector <pii> adj[maxn];
ll w[maxn], sz[maxn], h[maxn], d[maxn];
ll mn[maxk];
ll n, k;
ll inf = 1e9 + 7, ans = 1e9 + 7;
bool dead[maxn];
vector <ll> vec;

inline void dfs(ll v, ll p = -1){
	sz[v] = 1;
	vec.pb(v);
	for(auto u : adj[v]){
		if(u.F != p && !dead[u.F]){
			dfs(u.F, v);
			sz[v] += sz[u.F]; 
		}
	}
}
inline ll find_centroid(ll v, ll p, ll 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;
}

inline void DFS(ll v, ll p = -1){
	if(k - d[v] >= 0 && k - d[v] < maxk - 2){
		ans = min(mn[k - d[v]] + h[v], ans);
	}
	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);
		}
	}
	if(d[v] >= 0 && d[v] < maxk - 2){
		mn[d[v]] = min(h[v], mn[d[v]]);
	}
}

inline void solve(ll v){
	vec.clear();
	dfs(v);
	ll c = find_centroid(v, -1, sz[v]);
	dead[c] = true;
	h[c] = d[c] = 0;
	DFS(c);
	ans = min(ans, mn[k]);
	for(ll u : vec){
		if(d[u] >= 0 && d[u] < maxk - 2){
			mn[d[u]] = inf;
		}
	}
	for(auto x : adj[c]){
		if(!dead[x.F]){
			solve(x.F);
		}
	}
}
///*
int best_path(int N, int K, int H[][2], int L[]){
	n = N;
	k = K;
	
	for(int i = 0; i < n - 1; i ++){
		int x = H[i][0], y = H[i][1];
		adj[x].push_back({y, i});
		adj[y].push_back({x, i});
	}	
	for(int i = 0; i < n - 1; i ++)
		w[i] = L[i];
	
	for(int i = 0; i < maxk - 2; i ++){
		mn[i] = inf;
	}
	
	solve(0);
 
	if(ans >= inf){
		ans = -1;
	}
		
	return ans;
}
//*/
/*
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 < maxk - 2; i ++){
		mn[i] = inf;
	}
	solve(0);
	if(ans >= inf){
		cout << -1;
	}
	else{
		cout << ans;
	}
	return 0;
}
*/

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