Submission #933879

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
933879	2024-02-26T12:55:52 Z	089487	Treasure Hunt (CEOI11_tre)	C++14	100 / 100	499 ms	51356 KB

#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;
      |               ^~~~

Subtask #1
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	8 ms	33116 KB	Output is correct

Subtask #2
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	10 ms	33116 KB	Output is correct
2	Correct	6 ms	33372 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	426 ms	39256 KB	Output is correct

Subtask #4
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	499 ms	37964 KB	Output is correct
2	Correct	420 ms	48644 KB	Output is correct

Subtask #6
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	296 ms	37892 KB	Output is correct
2	Correct	470 ms	38028 KB	Output is correct

Subtask #7
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	227 ms	35500 KB	Output is correct

Subtask #8
10.0 / 10.0

#	Verdict	Execution time	Memory	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

Subtask #9
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	451 ms	37880 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	458 ms	38216 KB	Output is correct