Submission #1071515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1071515		isaachew	Tourism (JOI23_tourism)	C++17	100 / 100	819 ms	26824 KiB

tourism

#include <bits/stdc++.h>


/*
 HLD + Segtree + Segtree
 */
struct segtree2{//range sum segtree
    int size;
    std::vector<int> nodes;
    segtree2(){}
    void init(int n){
        size=n;
        nodes.resize(2*n-1);
    }
    void update(int p,int x,int nl,int nr,int ni){
        if(p<nl||p>=nr)return;
        if(nl+1>=nr){
            nodes[ni]+=x;
            return;
        }
        int nm=(nl+nr)/2;
        update(p,x,nl,nm,ni+1);
        update(p,x,nm,nr,ni+2*(nm-nl));
        nodes[ni]=nodes[ni+1]+nodes[ni+2*(nm-nl)];
    }
    int query(int l,int r,int nl,int nr,int ni){
        if(l<=nl&&r>=nr){
            return nodes[ni];
        }
        if(r<=nl||l>=nr)return 0;
        int nm=(nl+nr)/2;
        return query(l,r,nl,nm,ni+1)+query(l,r,nm,nr,ni+2*(nm-nl));
    }
};
segtree2 sumseg;
struct segtree{//segtree to keep track of values in the other segtree
    int size;
    std::vector<int> nodes;
    segtree(){}
    void init(int n){
        size=n;
        nodes.resize(2*n-1,-1);
    }
    void update(int l,int r,int x,int nl,int nr,int ni){//
        if(r<=nl||l>=nr)return;
        if(l<=nl&&r>=nr){
            if(nodes[ni]==-2){//recurse on a mix
                int nm=(nl+nr)/2;//reset everything below node
                update(l,r,-1,nl,nm,ni+1);
                update(l,r,-1,nm,nr,ni+2*(nm-nl));
            }else if(nodes[ni]>=0){
                //std::cout<<"["<<nl<<","<<nr<<") not at "<<nodes[ni]<<'\n';
                sumseg.update(nodes[ni],-(nr-nl),0,sumseg.size,0);
            }
            nodes[ni]=x;
            //std::cout<<"["<<nl<<","<<nr<<") at "<<nodes[ni]<<'\n';
            if(nodes[ni]!=-1)sumseg.update(nodes[ni],(nr-nl),0,sumseg.size,0);
            return;
        }
        int nm=(nl+nr)/2;
        if(nodes[ni]>=0){//pushdown
            nodes[ni+1]=nodes[ni];
            nodes[ni+2*(nm-nl)]=nodes[ni];
            nodes[ni]=-2;
        }
        update(l,r,x,nl,nm,ni+1);
        update(l,r,x,nm,nr,ni+2*(nm-nl));
        nodes[ni]=(nodes[ni+1]!=-1||nodes[ni+2*(nm-nl)]!=-1)?-2:-1;
    }
};
segtree mainseg;
int nids=0;
std::vector<int> parents;
std::vector<std::vector<int>> edges;//children
std::vector<int> depths;
std::vector<int> ssizes;
std::vector<int> ids;
std::vector<int> heavys;
std::vector<int> heavybs;
int dfs(int cur,int par){
    parents[cur]=par;
    for(int i:edges[cur]){
        if(i==par)continue;
        depths[i]=depths[cur]+1;
        ssizes[cur]+=dfs(i,cur);
        if(heavys[cur]==-1||ssizes[i]>ssizes[heavys[cur]])heavys[cur]=i;//replace heavy if necessary
    }
    return ssizes[cur];
}
void dfs2(int cur,int heavy){
    ids[cur]=nids++;
    heavybs[cur]=heavy;
    if(heavys[cur]!=-1)dfs2(heavys[cur],heavy);
    for(int i:edges[cur]){
        if(i==heavys[cur]||i==parents[cur])continue;
        dfs2(i,i);
    }
}
int main(){
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m,q;
    std::cin>>n>>m>>q;
    parents.resize(n);
    edges.resize(n);
    ids.resize(n);
    depths.resize(n);
    heavys.resize(n,-1);
    heavybs.resize(n);
    ssizes.resize(n,1);
    std::vector<int> spots;
    for(int i=0;i<n-1;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        edges[a].push_back(b);
        edges[b].push_back(a);
    }
    for(int i=0;i<m;i++){
        int x;
        std::cin>>x;
        x--;
        spots.push_back(x);
    }
    std::vector<std::pair<int,int>> queries;
    std::vector<int> results(q);
    std::vector<std::vector<int>> squeries(m);//indices per ending time
    for(int i=0;i<q;i++){
        int a,b;
        std::cin>>a>>b;
        a--,b--;
        queries.push_back({a,b});
        squeries[b].push_back(i);
    }
    dfs(0,0);
    dfs2(0,0);
    sumseg.init(m);
    mainseg.init(n);
    for(int i=0;i<m-1;i++){//go
        int src=spots[i],dst=spots[i+1];
        while(heavybs[src]!=heavybs[dst]){
            if(depths[heavybs[src]]>depths[heavybs[dst]]){
                mainseg.update(ids[heavybs[src]],ids[src]+1,i,0,n,0);
                src=parents[heavybs[src]];
            }else{
                mainseg.update(ids[heavybs[dst]],ids[dst]+1,i,0,n,0);
                dst=parents[heavybs[dst]];
            }
        }
        mainseg.update(std::min(ids[src],ids[dst]),std::max(ids[src],ids[dst])+1,i,0,n,0);
        for(int j:squeries[i+1]){
            results[j]=std::max(1,sumseg.query(queries[j].first,queries[j].second,0,m,0));//make sure at least 1 so paths like 3 3 3 visit city 3
        }
    }
    for(int j:squeries[0]){//random edge case: query ends in 1 -> only 1 city visited
        results[j]=1;
    }
    for(int i:results)std::cout<<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