제출 #1125703

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125703		PieArmy	Race (IOI11_race)	C++20	0 / 100	4 ms	4928 KiB

race

typedef long long ll;
ll pie(ll army){return (1ll<<army);}
#include <bits/stdc++.h>
#include "race.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;
	q.push({pos,0,0,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;
		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});
		}
	}
	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: 0 / 9
• Subtask 2: 0 / 12
• Subtask 3: 0 / 22
• Subtask 4: 0 / 57