Submission #1056205

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056205		vjudge1	Race (IOI11_race)	C++17	100 / 100	214 ms	32032 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
 
vector<pair<int,int>> v[200005];
int vis[200005],sub[200005],mpp[1000005];
int k;
int cev;
#define pb push_back
#define fi first
#define se second
 
inline void pre(int node,int ata){
	sub[node]=1;
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		pre(go.fi,node);
		sub[node]+=sub[go.fi];
	}
}
 
inline int find_centroid(int node,int ata,int val){
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		if(sub[go.fi]>=val/2)return find_centroid(go.fi,node,val);
	}
	return node;
}
 
inline void check(int node,int ata,int der,int kac){
	if(der>k)return ;
	if(mpp[k-der]!=-1)cev=min(cev,mpp[k-der]+kac);
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		check(go.fi,node,der+go.se,kac+1);
	}
}
 
inline void build(int node,int ata,int der,int kac){
	if(der>k)return ;
	if(mpp[der]==-1)mpp[der]=kac;
	else mpp[der]=min(mpp[der],kac);
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		build(go.fi,node,der+go.se,kac+1);
	}
}
 
inline void sifirla(int node,int ata,int der){
	if(der>k)return ;
	mpp[der]=-1;
	for(auto go:v[node]){
		if(go.fi==ata || vis[go.fi])continue;
		sifirla(go.fi,node,der+go.se);
	}
}
 
inline void solve(int c){
	pre(c,-1);
	c=find_centroid(c,-1,sub[c]);
	mpp[0]=0;
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		check(go.fi,c,go.se,1);
		build(go.fi,c,go.se,1);
	}
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		sifirla(go.fi,c,go.se);
	}
	vis[c]=1;
	for(auto go:v[c]){
		if(vis[go.fi])continue;
		solve(go.fi);
	}
}
 
int best_path(int N, int K, int H[][2], int L[]){
	k=K;
	memset(mpp,-1,sizeof(mpp));
	for(int i=0;i<N-1;i++){
		v[H[i][0]].pb({H[i][1],L[i]});
		v[H[i][1]].pb({H[i][0],L[i]});
	}
	cev=N+2;
	solve(0);
	if(cev==N+2)cev=-1;
	return cev;
}
 

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