Submission #23724

#	Time	Username	Problem	Language	Result	Execution time	Memory
23724		aleJF	Race (IOI11_race)	C++11	0 / 100	6 ms	4984 KiB

race

/*  race.cpp
 * 	by ale
 * Centroid Decomposition
 * */
#include <bits/stdc++.h>
#include "race.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 I oo=numeric_limits<LL>::max();

vector<pair<LL,I>> graph[MAXN];
void add_edge(I u,I v, LL ct)
{
	graph[u].pb(mp(ct,v));
	graph[v].pb(mp(ct,u));
}

I ans=oo;
LL _K;
bool mk[MAXN];
set<pair<LL,I>> cs;
I _sz[MAXN],h[MAXN];
I gsz(I u,I p=-1)
{
	_sz[u]=1;
	I mx=0,nxt=-1;
	efor(e,graph[u])
	{
		I v=e.sc;
		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,I 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,graph[u])
	{
		I v=e.sc;
		if(mk[v]||v==p)continue;
		calc(v,u,d+e.fr,dst+1);
	}
}
void updt(I u,I p,LL d,I dst=1)
{
	cs.ins(mp(d,dst));
	efor(e,graph[u])
	{
		I v=e.sc;
		if(mk[v]||v==p)continue;
		updt(v,u,d+e.fr,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,0));
	efor(e,graph[u])
	{
		I v=e.sc;
		if(mk[v])continue;
		calc(v,u,e.fr);
		updt(v,u,e.fr);
	}
	
	efor(e,graph[u])
	{
		I v=e.sc;
		if(mk[v])continue;
		cdecomp(v);
	}
}
	
int best_path(int N, int K, int H[][2], int L[])
{

	return -1;
}

Compilation message (stderr)

race.cpp:74:35: warning: overflow in implicit constant conversion [-Woverflow]
 const I oo=numeric_limits<LL>::max();
            ~~~~~~~~~~~~~~~~~~~~~~~^~

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