/* 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
race.cpp:74:35: warning: overflow in implicit constant conversion [-Woverflow]
const I oo=numeric_limits<LL>::max();
~~~~~~~~~~~~~~~~~~~~~~~^~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
6 ms |
4984 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
