제출 #892739

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
892739		alexander707070	Tourism (JOI23_tourism)	C++14	10 / 100	5052 ms	39120 KiB

tourism

#include<bits/stdc++.h>
#define MAXN 100007
using namespace std;

const int bucket_sz=200;

struct qr{
    int l,r,id;
}qs[MAXN];

struct node{
    int l,r;
}w[MAXN];

struct event{
    int type,ind,val,tim;
};

stack<event> st;

int n,m,q,a,b,tt,dist[MAXN],bucket[MAXN],l,r,cnt[MAXN],tim,sum,last,ans[MAXN];
int c[MAXN],num[MAXN],ret[MAXN],fr[MAXN];
vector<int> v[MAXN],euler;

void dfs(int x,int p,int d){
    tt++; num[x]=tt; ret[tt]=x;
    dist[x]=d;

    fr[x]=int(euler.size());
    euler.push_back(num[x]);

    for(int i=0;i<v[x].size();i++){
        if(v[x][i]==p)continue;
        dfs(v[x][i],x,d+1);

        euler.push_back(num[x]);
    }
}

bool li[4*MAXN][20];
int dp[4*MAXN][20];

int lg[4*MAXN],power[20];

void calc(){
    power[0]=1;
    for(int i=1;i<20;i++)power[i]=power[i-1]*2;
    lg[1]=0;
    for(int i=2;i<=4*n;i++)lg[i]=lg[i/2]+1;
}

int rmq(int i,int j){
    if(j==0)return euler[i];

    if(li[i][j])return dp[i][j];
    li[i][j]=true;

    dp[i][j]=min( rmq(i,j-1) , rmq(i+power[j-1],j-1) );
    return dp[i][j];
}

int lca(int x,int y){
    if(fr[x]>fr[y])swap(x,y);
    x=fr[x]; y=fr[y];

    return ret[ min( rmq(x,lg[y-x+1]) , rmq(y-power[lg[y-x+1]]+1,lg[y-x+1]) ) ];
}

int distance(int x,int y){
    if(x==0 or y==n+1)return 0;

    return dist[x]+dist[y]-2*dist[lca(x,y)];
}

bool cmp(qr fr,qr sc){
    if(bucket[fr.l]!=bucket[sc.l])return bucket[fr.l]<bucket[sc.l];
    return fr.r>sc.r;   
}

void insertv(int x,int y,int z){
    sum-=distance(ret[y],ret[z]);
    sum+=distance(ret[y],ret[x]);
    sum+=distance(ret[x],ret[z]);

    w[x].l=y; w[x].r=z;
    w[y].r=x; w[z].l=x;
}

void erasev(int x){
    st.push({1,w[x].l,x,tim});
    st.push({2,w[x].r,x,tim});

    w[w[x].l].r=w[x].r;
    w[w[x].r].l=w[x].l;
}

void rem(int x){
    if(x==0){
        tim++; return;
    }

    tim++;
    x=num[c[x]];
    cnt[x]--;

    if(cnt[x]!=0)return;

    st.push({3,0,sum,tim});

    sum-=distance(ret[w[x].l],ret[x]);
    sum-=distance(ret[x],ret[w[x].r]);
    sum+=distance(ret[w[x].l],ret[w[x].r]);

    erasev(x);
}

void undo(){
    while(!st.empty() and st.top().tim==tim){
        if(st.top().type==1){
            w[st.top().ind].r=st.top().val;
        }
        if(st.top().type==2){
            w[st.top().ind].l=st.top().val;
        }
        if(st.top().type==3){
            sum=st.top().val;
        }

        st.pop();
    }
    tim--;
}

void reset(){
    tim=sum=0;
    while(!st.empty())st.pop();
    for(int i=1;i<=n;i++)cnt[i]=0;
}

int edge(){
    int lx=w[0].r,rx=w[n+1].l;
    return distance(ret[lx],ret[rx]);
}

int main(){

    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin>>n>>m>>q;
    calc();

    for(int i=1;i<=n-1;i++){
        cin>>a>>b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1,0,0);

    w[0].l=n+1;
    w[n+1].r=0;
    ret[n+1]=n+1;

    for(int i=1;i<=m;i++){
        cin>>c[i];
        bucket[i]=i/bucket_sz;
    }

    for(int i=1;i<=q;i++){
        cin>>qs[i].l>>qs[i].r;
        qs[i].id=i;
    }

    sort(qs+1,qs+q+1,cmp);

    for(int i=1;i<=q;i++){
        if(i==1 or bucket[qs[i].l]!=bucket[qs[i-1].l]){
            reset();
            for(int f=bucket[qs[i].l]*bucket_sz;f<=m;f++){
                cnt[num[c[f]]]++;
            }

            last=0;
            for(int f=1;f<=n;f++){
                if(cnt[f]==0)continue;
                insertv(f,last,n+1);
                last=f;
            }
            l=bucket[qs[i].l]*bucket_sz;
            r=m;
        }

        while(r>qs[i].r){
            rem(r); r--;
        }

        while(l<qs[i].l){
            rem(l); l++;
        }

        ans[qs[i].id]=(sum+edge())/2;

        while(l>bucket[qs[i].l]*bucket_sz){
            undo(); l--; cnt[num[c[l]]]++;
        }

    }

    for(int i=1;i<=q;i++){
        cout<<ans[i]+1<<"\n";
    }

    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

tourism.cpp: In function 'void dfs(int, int, int)':
tourism.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<v[x].size();i++){
      |                 ~^~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 18
• Subtask 5: 0 / 24
• Subtask 6: 0 / 41