Submission #540593

#	Time	Username	Problem	Language	Result	Execution time	Memory
540593		jamezzz	Race (IOI11_race)	C++17	100 / 100	600 ms	61024 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;

#ifdef DEBUG
#define dbg(...) printf(__VA_ARGS__);
#define getchar_unlocked getchar
#else
#define dbg(...)
#endif
#define sf scanf
#define pf printf
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define mnto(x,y) x=min(x,(__typeof__(x))y)
#define mxto(x,y) x=max(x,(__typeof__(x))y)
#define INF 1023456789
#define LINF 1023456789123456789
#define all(x) x.begin(), x.end()
#define disc(x) sort(all(x));x.resize(unique(all(x))-x.begin());
typedef long long ll;
typedef long double ld;
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
typedef tuple<int, int, int, int> iiii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<pll> vll;
mt19937 rng(time(0));

#define mod 1000000007

#define maxn 200005

int N,K,ans=INF,sub[maxn],dis[maxn],num[maxn],mn[1000005];
bool mark[maxn];
vi nodes[maxn];
vii AL[maxn];

void dfs(int u,int p){
	sub[u]=1;
	for(auto[v,w]:AL[u]){
		if(mark[v]||v==p)continue;
		dfs(v,u);
		sub[u]+=sub[v];
	}
}

void dfs2(int u,int p,int s){
	if(s!=-1)nodes[s].pb(u);
	for(auto[v,w]:AL[u]){
		if(mark[v]||v==p)continue;
		dis[v]=dis[u]+w;
		if(dis[v]>=INF)dis[v]=INF;
		num[v]=num[u]+1;
		if(s==-1){
			nodes[v].clear();
			dfs2(v,u,v);
		}
		else dfs2(v,u,s);
	}
}

void decomp(int u){
	sub[u]=0;
	dfs(u,-1);
	int c=u;
	while(true){
		bool val=true;
		for(auto[v,w]:AL[c]){
			if(!mark[v]&&sub[v]<sub[c]&&sub[v]>sub[u]/2){
				val=false;
				c=v;break;
			}
		}
		if(val)break;
	}
	
	dis[c]=0;num[c]=0;
	dfs2(c,-1,-1);
	for(auto[v,w]:AL[c]){
		if(mark[v])continue;
		for(int i:nodes[v]){
			if(dis[i]>K)continue;
			ans=min(ans,mn[K-dis[i]]+num[i]);
		}
		for(int i:nodes[v]){
			if(dis[i]>K)continue;
			mn[dis[i]]=min(mn[dis[i]],num[i]);
		}
	}
	ans=min(ans,mn[K]);
	
	for(auto[v,w]:AL[c]){
		for(int i:nodes[v]){
			if(dis[i]>K)continue;
			mn[dis[i]]=INF;
		}
	}
	
	mark[c]=true;
	for(auto[v,w]:AL[c]){
		if(!mark[v])decomp(v);
	}
}

int best_path(int _N,int _K,int H[][2],int L[]){
	N=_N;K=_K;
	for(int i=0;i<=1000000;++i)mn[i]=INF;
	for(int i=0;i<N-1;++i){
		AL[H[i][0]].pb({H[i][1],L[i]});
		AL[H[i][1]].pb({H[i][0],L[i]});
	}
	decomp(0);
	return (ans!=INF)?ans:-1;
}

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