Submission #1303098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1303098		kokokai	Tourism (JOI23_tourism)	C++20	0 / 100	52 ms	14848 KiB

tourism

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define fi first
#define se second
const int N = 2e5+5;
const int LG = 19;
vector<int> adj[N];
int tin[N],tout[N],pos[N],euler[N],depth[N],timer,cntnode,h[N],lg2[N],arr[N];
int spt[N][LG];
int n,m,q;
void dfs(int u,int p){
    tin[u]=tout[u]=++timer;
    arr[timer]=u;
    h[u]=h[p]+1;
    euler[++cntnode]=u;
    pos[u]=cntnode;
    depth[cntnode]=h[u];
    for(int v:adj[u]){
        if(v==p) continue;
        dfs(v,u);
        euler[++cntnode]=u;
        depth[cntnode]=h[u];
    }
    tout[u]=timer;
}
int lca(int u,int v){
    int l=pos[u],r=pos[v];
    if(l>r) swap(l,r);
    int lg=lg2[r-l+1];
    int a=spt[l][lg];
    int b=spt[r-(1<<lg)+1][lg];
    int p=(depth[a] < depth[b] ? a:b);
    return euler[p];
}
int dist(int u,int v){
    int lc=lca(u,v);
    return h[u]+h[v]-2*h[lc];
}
struct que{
    int l,r,id;
}query[N];
int C[N];
ll ans[N];
ll cur=0;
set<int> s;
void add(int idx){
    int u=C[idx];
    int pos=tin[u];
    if(s.empty()){
        s.insert(pos);
        return;
    }
    auto it=s.lower_bound(pos);
    if(it != s.end()){
        int u1=arr[*it];
        if(it != s.begin()){
            --it;
            int u2=arr[*it];
            cur -= dist(u1,u2);
            cur += dist(u1,u);
            cur += dist(u,u2);
        }else{
            int u2=arr[*s.rbegin()];
            cur -= dist(u1,u2);
            cur += dist(u,u1);
            cur += dist(u,u2);
        }
    }
    else{
        --it;
        int u1=arr[*it];
        int u2=arr[*s.begin()];
        cur -= dist(u1,u2);
        cur += dist(u,u1);
        cur += dist(u,u2);
    }
    s.insert(pos);
}
void del(int idx){
    int u=C[idx];
    int pos=tin[u];
    auto it=s.upper_bound(pos);
    if(s.size() == 1){
        s.erase(pos);
        return;
    }
    if(it != s.end()){
        int u1=arr[*it];
        --it;
        if(it != s.begin()){
            --it;
            int u2=arr[*it];
            cur -= dist(u,u1);
            cur -= dist(u,u2);
            cur += dist(u1,u2);
        }else{
            int u2=arr[*s.rbegin()];
            cur -= dist(u,u2);
            cur -= dist(u,u1);
            cur += dist(u1,u2);
        }
    }else{
        --it;
        --it;
        int u1=arr[*s.begin()];
        int u2=arr[*it];
        cur -= dist(u,u2);
        cur -= dist(u,u1);
        cur += dist(u1,u2);
    }
    s.erase(pos);
}
int main(){
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);

    if(fopen("orzdevinwang.inp", "r")) {
        freopen("orzdevinwang.inp", "r", stdin);
        //freopen("orzdevinwang.out", "w", stdout);
    }
    lg2[1]=0;
    for(int i=2;i<N;i++) lg2[i]=lg2[i/2]+1;
    cin>>n>>m>>q;
    int can=sqrt(n);
    for(int i=1;i<n;i++){
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    dfs(1,0);
    for(int i=1;i<=cntnode;i++) spt[i][0]=i;
    for(int lg=1;lg<LG;lg++){
        for(int i=1;i+(1<<lg)-1<=cntnode;i++){
            int a=spt[i][lg-1];
            int b=spt[i+(1<<(lg-1))][lg-1];
            spt[i][lg] = (depth[a] < depth[b] ? a:b);
        }
    }
    for(int i=1;i<=m;i++) cin>>C[i];
    for(int i=1;i<=q;i++){
        int l,r;
        cin>>l>>r;
        query[i]={l,r,i};
    }
    sort(query+1,query+1+q,[&](que a,que b){
        int La=a.l/can;
        int Lb=b.l/can;
        if(La != Lb) return La < Lb;
        if(La%2==0) return a.r > b.r;
        else return a.r < b.r;
    });
    int curL=1,curR=0;
    for(int i=1;i<=q;i++){
        int L=query[i].l,R=query[i].r,id=query[i].id;
        while(curR < R) add(++curR);
        while(curR > R) del(curR--);
        while(curL < L) del(curL++);
        while(curL > L) add(--curL);
        ans[id]=cur/2 + 1;
    }
    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("orzdevinwang.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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