#include<bits/stdc++.h>
using namespace std;
#define eb emplace_back
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
int mx;
const int N=4e5+7;
const int INF=1e18;
const int K=20;
int ac[K][N];
int D[N];
int dep[N];
int d[N];
vector<int> vx;
vector<int> P;
void path(int a,int b);
int dig(int a,int b);
int Kthpnt(int k,int x){
int px=upper_bound(all(vx),x)-vx.begin()-1;
if(x-vx[px]>=k){
return x-k;
}
k-=(x-vx[px]);
x=px;
//debug("px",x,"left",k);
repd(i,K-1,0){
if(D[x]-D[ac[i][x]]<=k) k-=(D[x]-D[ac[i][x]]),x=ac[i][x];
}
if(k) x=P[x],k--;
else x=vx[x];
return x-k;
}
int kthac(int k,int x){
repd(i,K-1,0){
if((1<<i)&k) x=ac[i][x];
}
return x;
}
bool isanc(int a,int b){
if(dep[a]>dep[b]) return false;
//debug("isanc",a,b,dep[b]-dep[a],"th parent",kthac(dep[b]-dep[a],b),a);
return kthac(dep[b]-dep[a],b)==a;
}
int LCA(int a,int b){
if(isanc(a,b)) return a;
repd(i,K-1,0){
//debug(a,"check",ac[i][a],b,isanc(ac[i][a],b));
if(!isanc(ac[i][a],b)) a=ac[i][a];
}
return ac[0][a];
}
void Insert(int a,int b,int w){
ac[0][b]=a;
D[b]=D[a]+w;
dep[b]=dep[a]+1;
//debug("insert",a,"->",b);
rep(i,1,K-1){
ac[i][b]=ac[i-1][ac[i-1][b]];
//debug("Ac",b,":",1<<i,"=",ac[i][b]);
}
}
void init()
{
rep(i,0,K-1)ac[i][0]=0;
mx=1;
vx.eb(1);
P.eb(1);
dep[0]=0;
}
void path(int a, int b)
{
int p=upper_bound(all(vx),a)-vx.begin()-1;
P.eb(a);
// a-> mx+1 , mx+1->mx+b
vx.eb(mx+1);
mx+=b;
Insert(p,sz(vx)-1,a-vx[p]+1);
}
int dig(int a, int b)
{
bool swp=false;
if(a>b) swap(a,b),swp=true;
int pa=upper_bound(all(vx),a)-vx.begin()-1;
int pb=upper_bound(all(vx),b)-vx.begin()-1;
int w=LCA(pa,pb);
int d=D[pa]+D[pb]-D[w]*2+a-vx[pa]+b-vx[pb];
int Da=D[pa]-D[w]+a-vx[pa];
int Db=D[pb]-D[w]+b-vx[pb];
int da=dep[pa]-dep[w]-1;
int db=dep[pb]-dep[w]-1;
//debug("Da",da,"Db",db);
int a2=pa,b2=pb;
//debug(a,b,"a,b",vx[pa],vx[pb],"lca=",vx[w],"Dis=",D[pa]-D[w],"+",D[pb]-D[w],d);
//debug("D0",d);
if(da>=0){
repd(i,K-1,0){
if((1<<i)&da) a2=ac[i][a2];
}
//debug(a,"a2",vx[a2],":",P[a2]);
a2=P[a2];
Da-=(a2-vx[w]);
d-=(a2-vx[w]);
}
else a2=a,d-=(a2-vx[w]),Da-=(a2-vx[w]);
if(db>=0){
repd(i,K-1,0){
if((1<<i)&db) b2=ac[i][b2];
}
b2=P[b2];
Db-=(b2-vx[w]);
d-=(b2-vx[w]);
}
else b2=b,d-=(b2-vx[w]),Db-=(b2-vx[w]);
//debug("After",a2,b2,"res",d);
d+=abs(a2-b2);
if(a2<b2) Db+=b2-a2;
else Da+=a2-b2;
int req=d/2;
if(!swp) req=d-req;
//debug(a,b,"p",pa,pb,"lca =",LCA(pa,pb),"dis(a,b)","=",d,req);
if(Db>=req){
//debug("go from",b,req,"steps",":");
return Kthpnt(req,b);
//debug("get",req,)
//cout<<kthac(req,b)<<endl;
}
else{
//debug("go from",a,req,"Steps",":");
return Kthpnt(d-req,a);
//cout<<kthac(d-req,a)<<endl;
}
}
Compilation message
tre.cpp:10:15: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
10 | const int INF=1e18;
| ^~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
8 ms |
33116 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
10 ms |
33116 KB |
Output is correct |
| 2 |
Correct |
6 ms |
33372 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
426 ms |
39256 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
304 ms |
37412 KB |
Output is correct |
| 2 |
Correct |
234 ms |
38076 KB |
Output is correct |
| 3 |
Correct |
200 ms |
49752 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
499 ms |
37964 KB |
Output is correct |
| 2 |
Correct |
420 ms |
48644 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
296 ms |
37892 KB |
Output is correct |
| 2 |
Correct |
470 ms |
38028 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
227 ms |
35500 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
376 ms |
37992 KB |
Output is correct |
| 2 |
Correct |
143 ms |
51164 KB |
Output is correct |
| 3 |
Correct |
162 ms |
51356 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
451 ms |
37880 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
458 ms |
38216 KB |
Output is correct |
