Submission #953406

#	Time	Username	Problem	Language	Result	Execution time	Memory
953406		vjudge1	Race (IOI11_race)	C++17	100 / 100	440 ms	58296 KiB

race

#include "race.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int, int>
#define rep(a,b,c) for(int a=b; a<c; a++)
#define repa(a,b) for(auto a:b)
#define pb push_back

using namespace std;

const int lim=1e6+5;
bool vis[lim];
vector<pii> ady[lim];
int mn[lim], sz[lim], ans, n, k;
pii dis[lim];

void rem(int u){
	if(k>=dis[u].fi) mn[dis[u].fi]=1e9;
	vis[u]=true;
	repa(v,ady[u]) if(!vis[v.fi]) rem(v.fi);
	vis[u]=false;
}

void add(int u){
	if(k>=dis[u].fi) mn[dis[u].fi]=min(mn[dis[u].fi],dis[u].se);
	vis[u]=true;
	repa(v,ady[u]) if(!vis[v.fi]) add(v.fi);
	vis[u]=false;
}

void calc(int u){
	int x=1e9;
	if(k>=dis[u].fi) x=dis[u].se+mn[k-dis[u].fi];
	vis[u]=true;
	if(ans==-1 || ans>x) ans=x;
	repa(v,ady[u]) if(!vis[v.fi]) calc(v.fi);
	vis[u]=false;
}

void solve(int u,  int h, int e){
	dis[u]={h,e};
	vis[u]=true;
	repa(v,ady[u]) if(!vis[v.fi]) solve(v.fi,min(lim,h+v.se),e+1);
	vis[u]=false;
}

void pcalc(int u, int h){
	sz[u]=1;
	vis[u]=true;
	repa(v,ady[u]) if(!vis[v.fi]) pcalc(v.fi,h+1), sz[u]+=sz[v.fi];
	vis[u]=false;
}

int find_centroid(int u, int r){
	vis[u]=true;
	repa(v,ady[u]){
		if(!vis[v.fi] && sz[v.fi]>sz[r]/2){
			int x=find_centroid(v.fi,r);
			vis[u]=false;
			return x;
		}
	}
	vis[u]=false;
	return u;
}

void centroid(int u){
	pcalc(u,0);
	u = find_centroid(u,u);
	solve(u,0,0);
	vis[u]=true;
	repa(v,ady[u]) if(!vis[v.fi]) calc(v.fi), add(v.fi);
	repa(v,ady[u]) if(!vis[v.fi]) rem(v.fi);
	repa(v,ady[u]) if(!vis[v.fi]) centroid(v.fi);
	vis[u]=false;
}

int best_path(int N, int K, int H[][2], int L[]){
	rep(i,1,lim) mn[i]=1e9;
	mn[0]=0;
	rep(i,0,N-1){
		ady[H[i][0]].pb({H[i][1],L[i]});
		ady[H[i][1]].pb({H[i][0],L[i]});
	}
	n=N;
	k=K;
	ans=-1;
	centroid(0);
	if(ans>=1e9) ans=-1;
	return ans;
}

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