답안 #933872

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933872 2024-02-26T12:47:02 Z 089487 Treasure Hunt (CEOI11_tre) C++14
컴파일 오류
0 ms 0 KB
#include<bits/stdc++.h>
#define int long long
#define quick ios::sync_with_stdio(0);cin.tie(0);
#define rep(x,a,b) for(int x=a;x<=b;x++)
#define repd(x,a,b) for(int x=a;x>=b;x--)
#define lowbit(x) (x&-x)
#define F first
#define S second
#define sz(x) (int)(x.size())
#define all(x) x.begin(),x.end()
#define mp make_pair
#define eb emplace_back
using namespace std;
typedef pair<int,int> pii;
void debug(){
    cout<<"\n";
}
template <class T,class ... U >
void debug(T a, U ... b){
    cout<<a<<" ",debug(b...);
}
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]);
    }
}

signed main(){
	quick
    
    int n;
    cin>>n;
    rep(i,0,K-1)ac[i][0]=0;
    int mx=1;
    vx.eb(1);
    P.eb(1);
    dep[0]=0;
    rep(i,1,n){
        char c;
        int a,b;
        cin>>c>>a>>b;
        if(c=='P'){
            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);
        }
        else{
            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",":");
                cout<<Kthpnt(req,b)<<endl;
                //debug("get",req,)
                //cout<<kthac(req,b)<<endl;
            }
            else{
                //debug("go from",a,req,"Steps",":");
                cout<<Kthpnt(req,a)<<endl;
                //cout<<kthac(d-req,a)<<endl;
            }
        }
    }
    //debug("Vx");for(int i:vx) cout<<i<<" ";cout<<"\n";

}

Compilation message

/usr/bin/ld: /tmp/ccdDHYUM.o: in function `main':
tregrader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccl2qgBO.o:tre.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/ccdDHYUM.o: in function `main':
tregrader.cpp:(.text.startup+0x28): undefined reference to `init()'
/usr/bin/ld: tregrader.cpp:(.text.startup+0x81): undefined reference to `path(int, int)'
/usr/bin/ld: tregrader.cpp:(.text.startup+0xd5): undefined reference to `dig(int, int)'
collect2: error: ld returned 1 exit status