/* race.cpp
* by ale
* Centroid Decomposition
* */
#include "race.h"
#include <bits/stdc++.h>
using namespace std;
typedef int LL;
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);
}
}
I best_path(I n,LL k,I f[][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;
}
/*
*/
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3065 ms |
4984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3065 ms |
4984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3065 ms |
4984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
3065 ms |
4984 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
