Submission #865444

#	Time	Username	Problem	Language	Result	Execution time	Memory
865444		owoovo	Tourism (JOI23_tourism)	C++14	52 / 100	5053 ms	21548 KiB

tourism

#include<bits/stdc++.h>
#define pii pair<pair<int,int>,int>
#define F first 
#define S second
using namespace std;
int n,m,q,bit[100010],v[100010],c[100010],dp[25][100010],depth[100010],u;
vector<int> e[100010];
vector<pii> qu;
bool cmp(pii a, pii b){
    return a.S<b.S;
}
void modify(int x,int p){
    while(p<=m){
        bit[p]+=x;
        p+=p&(-p);
    }
    return ;
}
int que(int p){
    int ans=0;
    while(p){
        ans+=bit[p];
        p-=p&(-p);
    }
    return ans;
}
void dfs(int now,int last){
    dp[0][now]=last;
    depth[now]=depth[last]+1;
    for(auto x:e[now]){
        if(x==last)continue;
        dfs(x,now);
    }
    return;
}
int lca(int a,int b){
    if(depth[a]>depth[b])swap(a,b);
    for(int i=19;i>=0;i--){
        if(depth[a]+(1<<i)<=depth[b]){
            b=dp[i][b];
        }
    }
    if(a==b)return a;
    for(int i=19;i>=0;i--){
        if(dp[i][a]!=dp[i][b]){
            a=dp[i][a];
            b=dp[i][b];
        }
    }
    return dp[0][a];
}
int main(){
    u=0;
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int a,b;
        cin>>a>>b;
        e[a].push_back(b);
        e[b].push_back(a);
    }
    for(int i=1;i<=m;i++){
        cin>>v[i];
    }
    for(int i=0;i<q;i++){
        int a,b;
        cin>>a>>b;
        if(a==m)b=1,u++;
        qu.push_back({{a,b},i});
    }
    dfs(1,1);
    for(int i=1;i<=19;i++){
        for(int j=1;j<=n;j++){
            dp[i][j]=dp[i-1][dp[i-1][j]];
        }
    }
    sort(qu.begin(),qu.end());
    int now=q-1-u;

    for(int i=m-1;i>0;i--){
        
        int p=lca(v[i],v[i+1]);
        
        int nw=v[i];
        while(nw!=p){
            if(c[nw]>0)modify(-1,c[nw]);
            c[nw]=i;
            modify(1,i);
            nw=dp[0][nw];
        }
        nw=v[i+1];
        while(nw!=p){
            if(c[nw]>0)modify(-1,c[nw]);
            c[nw]=i;
            modify(1,i);
            nw=dp[0][nw];
        }
        if(c[p]>0)modify(-1,c[p]);
        c[p]=i;
        modify(1,i);
        while(now>=0&&qu[now].F.F==i){
            if(qu[now].F.F==qu[now].F.S){
                qu[now].F.S=1;
            }else{
                qu[now].F.S=que(qu[now].F.S-1);
            }
            now--;
        }
    }

    sort(qu.begin(),qu.end(),cmp);
    for(auto x:qu){
        cout<<x.F.S<<"\n"; 
    }
    return 0;
}

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