Submission #1125706

#	Time	Username	Problem	Language	Result	Execution time	Memory
1125706		PieArmy	Race (IOI11_race)	C++20	43 / 100	3095 ms	29084 KiB

race

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#define fr first
#define sc second
#define pb push_back
#define endl '\n'
#define mid ((left+right)>>1)
const ll inf=2000000000000000005;
const int sonsuz=2000000005;
using namespace std;
ll fpow(ll x,ll y,ll m=0){if(y<0){cout<<"powError";return -1;}if(m)x%=m;ll res=1;while(y>0){if(y&1)res*=x;x*=x;if(m){x%=m;res%=m;}y>>=1;}return res;}

int n,k;
int sub[200000];
vector<pair<int,int>>komsu[200000];

void dfs(int pos,int par){
	sub[pos]=1;
	for(auto x:komsu[pos]){
		if(x.fr==par||sub[x.fr]==-1)continue;
		dfs(x.fr,pos);
		sub[pos]+=sub[x.fr];
	}
}

int deco(int pos){
	dfs(pos,pos);
	int total=sub[pos];
	while(true){
		int nex=-1;
		for(auto x:komsu[pos]){
			if(sub[x.fr]==-1)continue;
			if(sub[x.fr]>sub[pos])continue;
			if(sub[x.fr]>total/2){
				nex=x.fr;
				break;
			}
		}
		if(nex==-1)break;
		pos=nex;
	}
	sub[pos]=-1;
	map<ll,int>mp;
	int res=sonsuz;
	queue<array<ll,4>>q;
	for(auto y:komsu[pos]){
		q.push({y.fr,y.sc,1,pos});
		while(q.size()){
			int loc=q.front()[0],dis=q.front()[1],adim=q.front()[2],las=q.front()[3];
			q.pop();
			if(dis>k)continue;
			if(mp[k-dis])res=min(res,adim+mp[k-dis]);
			for(auto x:komsu[loc]){
				if(x.fr==las)continue;
				if(sub[x.fr]==-1)continue;
				q.push({x.fr,dis+x.sc,adim+1,loc});
			}
		}
		q.push({y.fr,y.sc,1,pos});
		while(q.size()){
			int loc=q.front()[0],dis=q.front()[1],adim=q.front()[2],las=q.front()[3];
			q.pop();
			if(dis>k)continue;
			if(mp[dis]==0){
				mp[dis]=adim;
			}
			else mp[dis]=min(mp[dis],adim);
			for(auto x:komsu[loc]){
				if(x.fr==las)continue;
				if(sub[x.fr]==-1)continue;
				q.push({x.fr,dis+x.sc,adim+1,loc});
			}
		}
	}
	if(mp[k])res=min(res,mp[k]);
	for(auto x:komsu[pos]){
		if(sub[x.fr]==-1)continue;
		res=min(res,deco(x.fr));
	}
	return res;
}

int best_path(int N,int K,int H[][2],int L[]){
	n=N;
	k=K;
	for(int i=0;i<n-1;i++){
		komsu[H[i][0]].pb({H[i][1],L[i]});
		komsu[H[i][1]].pb({H[i][0],L[i]});
	}
	int ans=deco(1);
	if(ans==sonsuz)return -1;
	return ans;
}

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