제출 #1310448

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1310448		khangai11	경주 (Race) (IOI11_race)	C++20	0 / 100	1 ms	332 KiB

race

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
vector<vector<pair<ll,ll>>> g;
vector<ll> child;
vector<char> rm;
ll dfs(ll i,ll p){
	child[i]=1;
	for(auto x:g[i]){
		ll z=x.first;
		if(z!=p and rm[z]==0)
		child[i]+=dfs(z,i);
	}
	return child[i];
}
ll center(ll i,ll p,ll ts){
	ll n=ts/2;
	for(auto x:g[i]){
		ll z=x.first;
		if(z==p or rm[z]==1){
			continue;
		}
		if(child[z]>n){
			return center(z,i,ts);
		}
	}
	return i;
}
map<ll,ll> mp;
ll k,D=1e9;
void dfs1(ll i,ll p,map<ll,ll> &mp1,ll d,ll de){
	if(d>k){
		return;
	}
	if(mp1.find(d)==mp1.end()){
		mp1[d]=de;
	}else{
		mp1[d]=min(mp1[d],de);
	}
	if(mp.find(k-d)!=mp.end()){
		D=min(D,mp[k-d]+de);
	}
	for(auto z:g[i]){
		if(p==z.first or rm[z.first]==1){
			continue;
		}
		dfs1(z.first,i,mp1,d+z.second,de+1);
	}
}
void build(ll i){
	dfs(i,-1);
	ll c=center(i,-1,child[i]);
	rm[c]=1;
	for(auto z:g[c]){
		if(rm[z.first]==1){
			continue;
		}
		map<ll,ll> mp1;
		dfs1(z.first,c,mp1,z.second,1);
		for(auto x:mp1){
			if(mp.find(x.first)==mp.end()){
				mp[x.first]=x.second;
			}else{
				mp[x.first]=min(mp[x.first],x.second);
			}
		}
	}
	for(auto z:g[c]){
		if(rm[z.first]==0)
		build(z.first);
	}
}
ll best_path(int N,int K,int H[][2],int L[]){
	ll n;
	n=N;
	k=K;
	g.resize(n);
	rm.resize(n,0);
	child.resize(n);
	for(ll a=0;a<n-1;a++){
		ll u=H[a][0],v=H[a][1],x=L[a];
		g[u].push_back({v,x});
		g[v].push_back({u,x});
	}
	build(0);
	if(D==1e9){
		D=-1;
	}
	return D;
}
//signed main(){
//	ios::sync_with_stdio();
//	cin.tie(0);
//	cout.tie(0);
////	freopen("yinyang.in", "r", stdin);
////	freopen("yinyang.out", "w", stdout);
//	ll t=1;
////	cin>>t;
//	for(ll a=0;a<t;a++){
//		solve();
//	}
//}

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