oj.uz

답안 #933878

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
933878 2024-02-26T12:55:03 Z 089487 Treasure Hunt (CEOI11_tre) C++14
0 / 100
 547 ms 50852 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(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
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 8 ms 33372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 9 ms 33372 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 410 ms 50852 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 306 ms 49256 KB Output is correct
2 Incorrect 217 ms 49852 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 465 ms 49824 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 334 ms 49516 KB Output is correct
2 Incorrect 547 ms 49776 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 213 ms 41312 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 328 ms 49776 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 419 ms 49780 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 444 ms 49856 KB Output isn't correct
2 Halted 0 ms 0 KB -