Submission #1316524

#TimeUsernameProblemLanguageResultExecution timeMemory
1316524kokokaiTourism (JOI23_tourism)C++20
0 / 100
5095 ms25224 KiB
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 1e5+5;
const int LG = 18;
int anc[N][LG];
int lg2[N];
int spt[N][LG];
vector<int> adj[N];
vector<pair<int,int>> query[N];
int ans[N],sz[N],h[N];
int c[N];
int n,m,q;
struct node{
    int l,r,val;
    bool operator <  (const node &oth) const{
        return r < oth.r;
    }
};
set<node> s[N];
int chainhead[N],chainid[N],pos[N],curchain,curpos;
void dfs(int u,int p){
    sz[u]=1;
    h[u]=h[p]+1;
    anc[u][0]=p;
    for(int lg=1;lg<LG;lg++) anc[u][lg]=anc[anc[u][lg-1]][lg-1];
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        sz[u] += sz[v];
    }
}
int lca(int u,int v){
    if(h[u]<h[v]) swap(u,v);
    int d=h[u]-h[v];
    for(int lg=LG-1;lg>=0;lg--){
        if((d&(1<<lg))>0) u=anc[u][lg];
    }
    if(u==v) return u;
    for(int lg=LG-1;lg>=0;lg--){
        if(anc[u][lg] != anc[v][lg]){u=anc[u][lg],v=anc[v][lg];}
    }
    return anc[u][0];
}
void hld(int u,int p){
    if(!chainhead[curchain]){
        chainhead[curchain]=u;
    }
    chainid[u]=curchain;
    pos[u]=++curpos;
    int nxt=0;
    for(int v:adj[u]){
        if(v==p) continue;
        if(sz[v] > sz[nxt]) nxt=v;
    }
    if(nxt) hld(nxt,u);
    for(int v:adj[u]){
        if(v==p || v==nxt) continue;
        ++curchain;
        hld(v,u);
    }
}
int rangelca(int l,int r){
    int lg=lg2[r-l+1];
    return lca(spt[l][lg],spt[r-(1<<lg)+1][lg]);
}
ll fw[N];
void update(int idx,ll val){
    for(;idx<=n;idx+=idx&(-idx)) fw[idx]+=val;
}
ll get(int idx){
    ll res=0;
    for(;idx>0;idx-=idx&(-idx)) res+=fw[idx];
    return res;
}
void update1(int u,int val){
    while(1){

        while(s[chainid[u]].size()){
            int l1=s[chainid[u]].begin()->l;
            int r1=s[chainid[u]].begin()->r;
            int val1=s[chainid[u]].begin()->val;
            int l=h[chainhead[chainid[u]]];
            int id=chainid[u];
            int r=h[u];
            if(r1 <= r){
                update(n-val1+1,-(r1-l1+1));
                s[id].erase(s[id].begin());
            }else{
                if(l1 <= r){
                    update(n-val1+1,-(r1-l1+1));
                    s[id].erase(s[id].begin());
                    if(r+1 <= r1){
                        s[id].insert({r+1,r1,val1});
                        update(n-val1+1,r1-r);
                    }
                }
                break;
            }
        }

        int l=h[chainhead[chainid[u]]];
        int r=h[u];
        s[chainid[u]].insert({l,r,val});

        update(n-val+1,r-l+1);
        //if(val == 2) cerr<<l<<' '<<r<<'\n';
        if(chainid[u] == chainid[1]) break;

        u=anc[chainhead[chainid[u]]][0];
    }
}
signed main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);
    if(fopen("text.inp","r")){
        freopen("text.inp","r",stdin);
    }
    lg2[1]=0;
    for(int i=2;i<N;i++) lg2[i]=lg2[i/2]+1;
    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);
    }
    for(int i=1;i<=m;i++) cin>>c[i];
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        query[r].push_back({l,i});
    }
    dfs(1,0);
    hld(1,0);
    for(int i=1;i<=m;i++) spt[i][0]=c[i];
    for(int lg=1;lg<LG;lg++){
        for(int i=1;i+(1<<lg)-1<=m;i++){
            spt[i][lg]=lca(spt[i][lg-1],spt[i+(1<<(lg-1))][lg-1]);
        }
    }
    for(int r=1;r<=m;r++){
        update1(c[r],r);
        for(auto &[l,id]:query[r]){
            ans[id]=get(n-l+1) - h[anc[rangelca(l,r)][0]];
        }
    }
    for(int i=1;i<=q;i++) cout<<ans[i]<<'\n';
}

Compilation message (stderr)

tourism.cpp: In function 'int main()':
tourism.cpp:118:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |         freopen("text.inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...