Submission #1303677

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303677		zhangspicyuwu	Tourism (JOI23_tourism)	C++20	100 / 100	275 ms	28144 KiB

tourism

#include <bits/stdc++.h>
#define fi first
#define se second
#define pii pair<int,int>
#define pll pair<long long,long long>
#define ll long long
//#define int long long
using namespace std;
const int N=1e5+5,mod=1e9+7,imod=(mod+1)/2;
const long long inf=1e18;
vector<int> adj[N];
int n,m,q,par[N],head[N],pos[N],sz[N],h[N],up[N],idd,arr[N],a[17][N],ans[N];
void pre_dfs(int u,int p){
    h[u]=h[p]+1;
    par[u]=p;
    sz[u]=1;
    for(const int v:adj[u]){
        if(v==p) continue;
        pre_dfs(v,u);
        sz[u]+=sz[v];
    }
}
void hld(int u,int x){
    head[u]=x;
    pos[u]=++idd;
    arr[idd]=u;
    int t1=0;
    for(const int v:adj[u]){
        if(v==par[u]) continue;
        if(sz[v]>sz[t1]) t1=v;
    }
    if(t1) hld(t1,x);
    for(const int v:adj[u]){
        if(v==par[u] || v==t1) continue;
        hld(v,v);
    }
}
int lca(int u,int v){
    while(head[u]!=head[v]){
        if(h[head[u]]<h[head[v]]) swap(u,v);
        u=par[head[u]];
    }
    if(h[u]>h[v]) return v;
    else return u;
}
int lg[N],fen[N];
int getlca(int l,int r){
    const int t=lg[r-l+1];
    return lca(a[t][l],a[t][r-(1<<t)+1]);
}
void add(int u,int val){
    while(u){
        fen[u]+=val;
        u-=(u&-u);
    }
}
int get(int u){
    int ans=0;
    while(u<=m){
        ans+=fen[u];
        u+=(u&-u);
    }
    return ans;
}
int seg[4*N];
void down(int crr){
    if(seg[crr]){
        const int x=seg[crr]; seg[crr]=0;
        seg[crr*2]=seg[crr*2+1]=x;
    }
}
void upd(int crr,int l,int r,int lm,int rm,int val){
    if(l>rm || lm>r) return;
    if(lm<=l && r<=rm){
        seg[crr]=val;
        return;
    }
    down(crr);
    int mid=l+r>>1;
    upd(crr*2,l,mid,lm,rm,val);
    upd(crr*2+1,mid+1,r,lm,rm,val);
}
int get(int crr,int l,int r,int id){
    if(l==r) return seg[crr];
    down(crr);
    int mid=l+r>>1;
    if(id<=mid) return get(crr*2,l,mid,id);
    else return get(crr*2+1,mid+1,r,id);
}
void upd(int u,const int c){
    while(u){
        upd(1,1,n,pos[head[u]],pos[u],c);
        u=par[head[u]];
    }
}
vector<pii> event[N];
signed main(){
    //freopen("GAME.inp","r",stdin);
    //freopen("MESSAGE.out","w",stdout);
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin>>n>>m>>q;
    for(int i=1;i<n;i++){
        int u,v; cin>>u>>v;
        adj[u].push_back(v); adj[v].push_back(u);
    }
    pre_dfs(1,0); hld(1,1);
    for(int i=1;i<=m;i++) cin>>a[0][i];
    for(int i=2;i<=m;i++) lg[i]=lg[i/2]+1;
    for(int j=1;j<17;j++){
        for(int i=1;i+(1<<j)-1<=m;i++){
            a[j][i]=lca(a[j-1][i],a[j-1][i+(1<<j-1)]);
        }
    }
    for(int i=1;i<=q;i++){
        int l,r; cin>>l>>r;
        event[r].push_back({l,i});
    }
    for(int i=1;i<=m;i++){
        int u=a[0][i];
        while(u && get(1,1,n,pos[u])==0){
            u=par[u];
        }
        while(u){
            const int col=get(1,1,n,pos[u]),nw=up[col];
            //cout<<"U: "<<u<<" "<<col<<"\n";
            add(col,h[nw]-h[u]);
            up[col]=u;
            u=nw;
        }
        u=a[0][i]; add(i,h[u]); upd(u,i);
        for(const pii j:event[i]){
            ans[j.se]=get(j.fi);
            int v=par[getlca(j.fi,i)];
            while(v){
                const int col=get(1,1,n,pos[v]),nw=up[col];
                if(col>=j.fi) ans[j.se]-=h[v]-h[nw];
                //cout<<"G: "<<v<<" "<<col<<"\n";
                v=nw;
            }
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<"\n";
}

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