제출 #748956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
748956		WongChun1234	Tourism (JOI23_tourism)	C++14	100 / 100	1112 ms	32332 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
const int N=100050;
int n,m,q,u,v,c[N],sz[N],ch[N],pre[N],post[N],lift[20][N],pt;
int hd[N],rpar[N],bit[N],lcaa,ans[N];
vector<int> adj[N];
vector<pair<int,int>> qs[N];
set<pair<int,int>> s;
void calcsize(int nde,int par){
    sz[nde]=1;
    for (int i:adj[nde]) if (i!=par){
        calcsize(i,nde);
        sz[nde]+=sz[i];
        if (sz[i]>sz[ch[nde]]) ch[nde]=i;
    }
}
void prehld(int nde,int par){
    lift[0][nde]=rpar[nde]=par;
    for (int i=1;i<19;i++) lift[i][nde]=lift[i-1][lift[i-1][nde]];
    pre[nde]=++pt;
    if (sz[nde]>1){
        hd[ch[nde]]=hd[nde];
        prehld(ch[nde],nde);
    }
    for (int i:adj[nde]) if (i!=par&&i!=ch[nde]){
        hd[i]=i;
        prehld(i,nde);
    }
    post[nde]=pt;
}
bool isa(int a,int b){
    return pre[a]<=pre[b]&&post[a]>=post[b];
}
int lca(int a,int b){
    if (isa(a,b)) return a;
    if (isa(b,a)) return b;
    for (int i=18;~i;i--) if (!isa(lift[i][a],b)) a=lift[i][a];
    return rpar[a];
}
void modify(int q,int v){
    for (;q<N;q+=q&-q) bit[q]+=v;
}
int query(int q){
    int ret=0;
    for (;q;q-=q&-q) ret+=bit[q];
    return ret;
}
vector<pair<pair<int,int>,int>> del;
int curr[N];
void add(int l,int r,int v){
	//cout<<"add "<<l<<" "<<r<<" "<<v<<"\n";
	//for (auto i:s) cout<<(i).first<<" "<<(i).second<<" ins\n";
    set<pair<int,int>>::iterator it;
    del.clear();
    it=s.upper_bound({l,INT_MIN});
    if ((*it).second>0) it--;
    while ((*it).second&&(*it).first<=r){
    	//cout<<(*it).first<<" "<<(*it).second<<"!\n";
    	int st=(*it).first;
    	it++;
    	s.erase(prev(it));
    	del.push_back({{st,(*it).first},(*it).second});
        modify((*it).second,-((*it).first-st+1));
        it++;
        s.erase(prev(it));
    }
    for (auto i:del){
    	if (i.first.first<l) s.insert({i.first.first,-i.second}),s.insert({l-1,i.second}),modify(i.second,l-i.first.first);
    	if (i.first.second>r) s.insert({r+1,-i.second}),s.insert({i.first.second,i.second}),modify(i.second,i.first.second-r);
	}
    s.insert({l,-v});
    s.insert({r,v});
    modify(v,r-l+1);
    //cout<<"end\n";
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>m>>q;
    for (int i=1;i<n;i++){
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    calcsize(1,1);
    hd[1]=1;
    prehld(1,1);
    for (int i=1;i<=m;i++) cin>>c[i];
    for (int i=1;i<=q;i++){
        cin>>u>>v;
        qs[v].push_back({u,i});
    }
    //for (int i=1;i<=n;i++) cout<<i<<" "<<hd[i]<<" "<<rpar[i]<<"\n";
    s.insert({0,0});
    s.insert({INT_MAX,0});
    for (int i=1;i<=m;i++){
        if (i>1){
            u=c[i-1];
            v=c[i];
            lcaa=lca(u,v);
        	//cout<<u<<"-"<<v<<"\n";
            while (hd[u]!=hd[lcaa]){
            	//cout<<u<<"!\n";
                add(pre[hd[u]],pre[u],i-1);
                u=rpar[hd[u]];
            }
            while (hd[v]!=hd[lcaa]){
            	//cout<<v<<"?\n";
                add(pre[hd[v]],pre[v],i-1);
                v=rpar[hd[v]];
            }
            add(min(pre[u],pre[v]),max(pre[u],pre[v]),i-1);
        }
        //cout<<i<<":\n";
        //for (auto j:s) cout<<j.first<<" "<<j.second<<"\n";
        for (auto j:qs[i]){
            ans[j.second]=(j.first==i?1:query(m)-query(j.first-1));
        }
    }
    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