Submission #1236753

#	Time	Username	Problem	Language	Result	Execution time	Memory
1236753		minhpk	Tourism (JOI23_tourism)	C++20	0 / 100	5094 ms	53708 KiB

tourism

#include <bits/stdc++.h>

using namespace std;
vector <int> z[1000005];
int sta[1000005],fin[1000005],euler[1000005];
int high[1000005];
int tour;
int st[300001][21];
int logarit[1000005];
int l,r;
void dfs(int i,int par){
     tour++;
     sta[i]=tour;
     euler[tour]=i;

     for (auto p:z[i]){
         if (p==par){
             continue;
         }
         high[p]=high[i]+1;
         dfs(p,i);
         tour++;
         euler[tour]=i;
     }

     tour++;
     fin[i]=tour;
     euler[tour]=i;
}
void buildst(){
    for (int i=1;i<=tour;i++){
         st[i][0]=euler[i];
    }

    for (int j=1;(1<<j)<=tour;j++){
         for (int i=1;i+(1<<j)-1<=tour;i++){
              int l=st[i][j-1];
              int r=st[i+(1<<(j-1))][j-1];

              if (high[l]<high[r]){
                 st[i][j]=l;
              }else{
                 st[i][j]=r;
              }
         }
    }
}
int lca(int x,int y){
    int l=min(sta[x],sta[y]);
    int r=max(sta[x],sta[y]);
    int j=logarit[r-l+1];
    int idx1=st[l][j];
    int idx2=st[r-(1<<j)+1][j];
    if (high[idx1]<high[idx2]){
        return idx1;
    }else{
        return idx2;
    }
}


int block;
int t[1000005];
struct node{
      int l,r,id;
};
node q[1000005];
bool cmp(node a,node b){
     int blocka=a.l/block;
     int blockb=b.l/block;

     if (blocka!=blockb){
         return blocka<blockb;
     }
     return a.r<b.r;
}
struct compare{
     bool operator()(int a,int b){
          return sta[a]>sta[b];
     }
};
multiset<int> s;
int sum=0;
int res[1000005];
int cal(int x,int y){
    return high[x]+high[y]-2*high[lca(x,y)];
}
void add(int x){
     x=t[x];
     if (!s.size()){
         s.insert(x);
         return;
     }
     auto it=s.lower_bound(x);
     if (it==s.begin()){
         auto it1=s.rbegin();
         sum-=cal(*it1,*it);
         sum+=cal(*it1,x);
         sum+=cal(*it,x);
     }else if (it==s.end()){
         --it;
         auto it1=s.begin();
         sum-=cal(*it1,*it);
         sum+=cal(*it1,x);
         sum+=cal(*it,x);
     }else{
         auto it1=it;
         --it1;
         sum-=cal(*it1,*it);
         sum+=cal(*it1,x);
         sum+=cal(*it,x);
     }


     s.insert(x);
}


void del(int x){
     x=t[x];
     auto it=s.lower_bound(x);
     if (s.size()==1){
         s.erase(it);
         return;
     }
     auto pre=s.end();
     --pre;
     if (it==s.begin()){
         auto it1=s.rbegin();
         auto it2=it;
         ++it2;
         sum+=cal(*it1,*it2);
         sum-=cal(*it1,*it);
         sum-=cal(*it2,*it);
     }else if (it==pre){
         auto it1=s.begin();
         auto it2=it;
         --it2;
         sum+=cal(*it1,*it2);
         sum-=cal(*it1,*it);
         sum-=cal(*it2,*it);
     }else{
         auto it1=it;
         auto it2=it;
         --it2;
         it1++;
         sum+=cal(*it1,*it2);
         sum-=cal(*it1,*it);
         sum-=cal(*it2,*it);
     }
     s.erase(it);
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,c;
    cin >> a >> b >> c;
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         z[y].push_back(x);
    }
    logarit[2]=1;
    for (int i=3;i<=1e6;i++){
         logarit[i]=logarit[i/2]+1;
    }
    dfs(1,1);
    buildst();

    block=sqrt(b);
    for (int i=1;i<=b;i++){
         cin >> t[i];
    }
    for (int i=1;i<=c;i++){
         int x,y;
         cin >> x >> y;
         q[i]={x,y,i};
    }
    sort(q+1,q+1+c,cmp);
    l=q[1].l;
    r=q[1].r;

    for (int i=l;i<=r;i++){
         add(i);
    }
    res[q[1].id]=sum/2+1;
//    for (int i=1;i<=c;i++){
//         cout << q[i].id << " ";
//    }
//    cout << "\n";
//    cerr << "\n";
//    cerr <<  1 << " " <<  q[1].id << "\n";
    for (int i=2;i<=c;i++){
         while (l>q[i].l){
              l--;
              add(l);
         }
         while (r<q[i].r){
              r++;
              add(r);
         }

        while (l<q[i].l){
              del(l);
              l++;
         }
         while (r>q[i].r){
              del(r);
              r--;
         }
         res[q[i].id]=sum/2+1;
//         cerr <<  i << " " <<  q[i].id << " " <<    s.size() << " " << *s.begin() << "\n";
    }
    for (int i=1;i<=c;i++){
         cout << res[i] << "\n";
    }

    return 0;
}

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