| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 933875 | 089487 | Treasure Hunt (CEOI11_tre) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define int long long
#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;
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;
int 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(req,a);
//cout<<kthac(d-req,a)<<endl;
}
}