제출 #412488

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
412488		20160161simone	경주 (Race) (IOI11_race)	C++14	0 / 100	6 ms	8140 KiB

race

#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=2e5+10;
struct edge{
	ll to,nxt,w;
}ln[N*2];
ll idx[N],topln;
void add_edge(ll u,ll v,ll w){
	ln[++topln]=(edge){v,idx[u],w},idx[u]=topln;
	ln[++topln]=(edge){u,idx[v],w},idx[v]=topln;
}

ll k;
ll S,rt,rtmx,vis[N],siz[N];
void init(ll x){S=x,rt=0,rtmx=N;}
void findrt(ll x,ll fa){
	ll mx=0; siz[x]=1;
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(ln[i].to==fa || vis[ln[i].to]) continue;
		findrt(ln[i].to,x);
		siz[x]+=siz[ln[i].to];
		mx=max(mx,siz[ln[i].to]);
	}
	mx=max(mx,S-siz[x]);
	if(mx<rtmx) mx=rtmx,rt=x;
}

const ll K=1e6+10;
ll ans=N,dis[N],top=0,cnt[K];
struct node{
	ll w,d;
}mrk[N];
ll mrk2[N];
void Count(ll x,ll fa,ll d){
	if(dis[x]>k || d>=ans) return;
	mrk[++top]=(node){dis[x],d};
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(ln[i].to==fa || vis[ln[i].to]) continue;
		dis[ln[i].to]=dis[x]+ln[i].w;
		Count(ln[i].to,x,d+1);
	}
}
void solve(ll x){
	ll top2=0;
	cnt[0]=0;
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(vis[ln[i].to]) continue;
		top=0;
		dis[ln[i].to]=ln[i].w,Count(ln[i].to,x,1);
		for(ll j=1;j<=top;j++)
			if(cnt[k-mrk[j].w]!=cnt[K-1]){
				ans=min(ans,mrk[j].d+cnt[k-mrk[j].w]);
			}
		for(ll j=1;j<=top;j++){
			cnt[mrk[j].w]=min(cnt[mrk[j].w],mrk[j].d);
			mrk2[++top2]=mrk[j].w;
		}
	}
	for(ll i=1;i<=top2;i++) cnt[mrk2[i]]=cnt[K-1];
}
void dfs(ll x){
	vis[x]=1;
	solve(x);
	for(ll i=idx[x];i;i=ln[i].nxt){
		if(vis[ln[i].to]) continue;
		init(siz[ln[i].to]),findrt(ln[i].to,0);
		dfs(rt);
	}
}

int best_path(int N, int K, int H[][2], int L[])
{
	memset(cnt,127,sizeof(cnt));
	
	ll n=N;
	k=K;
	for(ll i=1;i<n;i++){
		ll u=H[i-1][0]+1,v=H[i-1][1]+1,w=L[i-1];
		add_edge(u,v,w);
	}
	init(n),findrt(1,0);
	dfs(1);
	if(ans==N) return -1;
	else return ans;
}

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