Submission #23712

#	Time	Username	Problem	Language	Result	Execution time	Memory
23712		aleJF	경주 (Race) (IOI11_race)	C++11	Compilation error	0 ms	0 KiB

race

/*  race.cpp
 * 	by ale
 * Centroid Decomposition
 * */
#include "race.h"
#include <bits/stdc++.h>

using namespace std;

typedef int I;
typedef double D;
typedef long long int LL;
typedef long double LD;
typedef complex<D> CPX;
typedef pair<I,I> PII;
typedef pair<LL,LL> PLL;
typedef pair<D,LL> PDLL;
typedef pair<D,I> PDI;

typedef vector<I> VI;
typedef vector<LL> VLL;
typedef vector<D> VD;
typedef vector<LD> VLD;
typedef vector<CPX> VCPX;
typedef vector<PII> VPII;
typedef vector<PLL> VPLL;
typedef vector<PDLL> VPDLL;
typedef vector<PDI> VPDI;
typedef set<I> SI;
typedef set<LL> SLL;
typedef set<D> SD;
typedef set<LD> SLD;
typedef set<CPX> SCPX;
typedef set<PII> SPII;
typedef set<PLL> SPLL;
typedef set<PDLL> SPDLL;
typedef set<PDI> SPDI;

#define endl '\n'
#define fr first
#define sc second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define mt make_tuple
#define ins insert
#define ers erase
#define lb lower_bound
#define ub upper_bound
#define fd find
#define sz(v) ((I)(v).size())
#define ifor(i,st,ed) for(I i=(st);i<=(ed);++i)
#define dfor(i,st,ed) for(I i=(st);i>=(ed);--i)
#define efor(it,x) for(auto it:(x))
#define all(x) (x).begin(),(x).end()
#define srt(x) sort(all(x))
#define srtl(x,l) sort(all(x),(l))
#define srtn(x,n) sort((x),(x)+(n))
#define srtnl(x,n,l) sort((x),(x)+(n),(l))
#define cout(x) cout<<fixed<<setprecision((x))
#define pln1(a) cout<<a<<endl
#define pln2(a,b) cout<<(a)<<' '<<(b)<<endl
#define pln3(a,b,c) cout<<(a)<<' '<<(b)<<' '<<(c)<<endl
#define pln4(a,b,c,d) cout<<(a)<<' '<<(b)<<' '<<(c)<<' '<<(d)<<endl
#define ppln1(p,a) cout(p)<<a<<endl
#define ppln2(p,a,b) cout(p)<<(a)<<' '<<(b)<<endl
#define ppln3(p,a,b,c) cout(p)<<(a)<<' '<<(b)<<' '<<(c)<<endl
#define ppln4(p,a,b,c,d) cout(p)<<(a)<<' '<<(b)<<' '<<(c)<<' '<<(d)<<endl
#define debug(x) cerr<<#x<<" = "<<x<<endl

//#define DEBUG_MODE    //DEBUG FLAG

const I MAXN=2e5+7;
const LL oo=numeric_limits<LL>::max();

I H[MAXN][2];
LL L[MAXN];
I _next(I u,I e)
{
	if(u==H[e][0])return H[e][1];
	return H[e][0];
}
VI incidence[MAXN];
LL ans=oo,K;
bool mk[MAXN];
SPLL cs;
I _sz[MAXN],h[MAXN];
I gsz(I u,I p=-1)
{
	_sz[u]=1;
	I mx=0,nxt=-1;
	efor(e,incidence[u])
	{
		I v=_next(u,e);
		if(mk[v]||v==p)continue;
		I ss=gsz(v,u);
		if(ss>mx)mx=ss,nxt=v;
		_sz[u]+=ss;
	}
	h[u]=nxt;
	return _sz[u];
}
I gc(I u,I sz)
{
	sz>>=1;
	I last=u;
	while(u!=-1&&_sz[u]>sz)last=u,u=h[u];
	return last;
}
void calc(I u,I p,LL d,LL dst=1)
{
	LL k=K-d;
	if(k>=0)
	{
		auto lw=cs.lb(mp(k,0));
		if(lw!=cs.end()&&(*lw).fr==k)
			ans=min(ans,dst+(*lw).sc);
	}
	efor(e,incidence[u])
	{
		I v=_next(u,e);
		if(mk[v]||v==p)continue;
		calc(v,u,d+L[e],dst+1);
	}
}
void updt(I u,I p,LL d,LL dst=1)
{
	cs.ins(mp(d,dst));
	efor(e,incidence[u])
	{
		I v=_next(u,e);
		if(mk[v]||v==p)continue;
		updt(v,u,d+L[e],dst+1);
	}
}
void cdecomp(I u=0)
{
	I sz=gsz(u);
	u=gc(u,sz);
	mk[u]=true;
	//cerr<<u<<endl;
	
	cs.clear();
	cs.ins(mp(0LL,0LL));
	efor(e,incidence[u])
	{
		I v=_next(u,e);
		if(mk[v])continue;
		calc(v,u,L[e]);
		updt(v,u,L[e]);
	}
	
	efor(e,incidence[u])
	{
		I v=_next(u,e);
		if(mk[v])continue;
		cdecomp(v);
	}
}

LL best_path(I& n,LL& k,I f[MAXN][2],LL l[])
{
	
	K=k;
	ifor(i,1,n-1)
	{
		incidence[f[i][0]].pb(i);
		incidence[f[i][1]].pb(i);
		H[i][0]=f[i][0];
		H[i][1]=f[i][1];
	}
	cdecomp();
	return ans!=oo?ans:-1;
}
/*

*/

Compilation message (stderr)

/tmp/ccZi4KB1.o: In function `main':
grader.cpp:(.text.startup+0x20): undefined reference to `best_path(int, int, int (*) [2], int*)'
collect2: error: ld returned 1 exit status