Submission #1192761

#	Time	Username	Problem	Language	Result	Execution time	Memory
1192761		adhityamv	Tourism (JOI23_tourism)	C++20	28 / 100	5095 ms	78396 KiB

tourism

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
#include <stack>
using namespace std;
#define int long long
#define mp make_pair
#define fi first
#define pii pair<int,int>
#define se second
const int INF=1000000000000000000;
//const int INF=1e9;
const int N=1000000;
//const int M=998244353;
const int ln=20;
template<typename T>
std::ostream& operator<< (std::ostream& os,pair<T,T> p){
    return os << p.fi << "," << p.se << " ";
}
vector<int> edges[N];
int parent[N];
int depth[N];
int lpos[N];
int rpos[N];
vector<int> et;
vector<int> det;
void dfs(int u,int p){
    parent[u]=p;
    lpos[u]=rpos[u]=et.size();
    et.push_back(u);
    det.push_back(depth[u]);
    for(int v:edges[u]){
        if(v==p) continue;
        depth[v]=depth[u]+1;
        dfs(v,u);
        rpos[u]=et.size();
        et.push_back(u);
        det.push_back(depth[u]);
    }
}
int sq=300;
int pow2[N];
void solve(){
    int n,m,q;
    cin >> n >> m >> q;
    for(int i=0;i<n-1;i++){
        int u,v;
        cin >> u >> v;
        u--,v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
    }
    depth[0]=0;
    dfs(0,-1);
    int c[m];
    for(int i=0;i<m;i++){
        cin >> c[i];
        c[i]--;
    }
    pair<pii,int> queries[q];
    for(int i=0;i<q;i++){
        int l,r;
        cin >> l >> r;
        l--;
        queries[i]=mp(mp(l,r),i);
    }
    sort(queries,queries+q,[&](pair<pii,int> p1,pair<pii,int> p2){
        return mp(p1.fi.fi/sq,(2*((p1.fi.fi/sq)%2)-1)*p1.fi.se)<mp(p2.fi.fi/sq,(2*((p2.fi.fi/sq)%2)-1)*p2.fi.se);
    });
    int sptb[2*n-1][ln];
    for(int i=0;i<2*n-1;i++) sptb[i][0]=det[i];
    for(int j=0;j<ln-1;j++){
        for(int i=0;i<2*n-1;i++){
            if(i+(1<<j)>=2*n-1){
                sptb[i][j+1]=sptb[i][j];
            } else sptb[i][j+1]=min(sptb[i][j],sptb[i+(1<<j)][j]);
        }
    }
    auto lca=[&](int u,int v){
        int l=min(lpos[u],lpos[v]);
        int r=max(lpos[u],lpos[v])+1;
        int sz=pow2[r-l];
        int o1=sptb[l][sz];
        int o2=sptb[r-(1<<sz)][sz];
        return min(o1,o2);
    };
    int cl=0;
    int cr=0;
    int cans=0;
    int ans[q];    
    //for(int i:et) cout << i << " ";
    //cout << "\n";
    multiset<int> lposes;
    for(int i=0;i<q;i++){
        int l=queries[i].fi.fi;
        int r=queries[i].fi.se;
        int ind=queries[i].se;
        auto inc=[&](int ci)->void{
            //cout << ci << ">?\n";
            auto it=lposes.insert(lpos[c[ci]]);
            auto nit=next(it,1);
            cans+=depth[c[ci]];
            if(it==lposes.begin() && nit==lposes.end()){
                return;
            }
            if(it==lposes.begin() && nit!=lposes.end()){
                cans-=lca(c[ci],et[*nit]);
                return;
            }
            auto pit=next(it,-1);
            if(nit==lposes.end()){
                cans-=lca(c[ci],et[*pit]);
                return;
            }
            cans+=lca(et[*pit],et[*nit]);
            cans-=lca(c[ci],et[*pit]);
            cans-=lca(c[ci],et[*nit]);
        };
        auto rem=[&](int ci)->void{
            auto it=lposes.find(lpos[c[ci]]);
            auto nit=next(it,1);
            cans-=depth[c[ci]];
            if(it==lposes.begin() && nit==lposes.end()){
                lposes.erase(it);
                return;
            }
            if(it==lposes.begin() && nit!=lposes.end()){
                cans+=lca(c[ci],et[*nit]);
                lposes.erase(it);
                return;
            }
            auto pit=next(it,-1);
            if(nit==lposes.end()){
                cans+=lca(c[ci],et[*pit]);
                lposes.erase(it);
                return;
            }
            cans-=lca(et[*pit],et[*nit]);
            cans+=lca(c[ci],et[*pit]);
            cans+=lca(c[ci],et[*nit]);
            lposes.erase(it);
        };
        while(cr<r){
            inc(cr);
            cr++;
        }
        while(cl>l){
            cl--;
            inc(cl);
        }
        while(cl<l){
            rem(cl);
            cl++;
        }
        while(cr>r){
            cr--;
            rem(cr);
        }
        
        ans[ind]=cans-lca(et[*lposes.begin()],et[*lposes.rbegin()]);
    }
    for(int i=0;i<q;i++) cout << ans[i]+1 << "\n";
}
signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    pow2[1]=0;
    for(int i=2;i<N;i++){
        if(i==(1<<(pow2[i-1]+1))) pow2[i]=pow2[i-1]+1;
        else pow2[i]=pow2[i-1];
    }
    int t;
    //cin >> t;
    t=1;
    while(t--) solve();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n"; 
}

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