oj.uz

Submission #917256

# Submission time Handle Problem Language Result Execution time Memory
917256 2024-01-27T14:14:38 Z huutuan Tourism (JOI23_tourism) C++14
0 / 100
 2045 ms 53272 KB 
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2")
#include<bits/stdc++.h>

using namespace std;

// #define int long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define isz(x) ((int)x.size())
#define sumof(x) accumulate(all(x), 0ll)

const int N=1e5+1, S=400, LG=18;

struct Query{
   int l, r, i;

   Query(int a=0, int b=0, int c=0): l(a), r(b), i(c){}

   bool operator<(const Query& x){
      return l/S!=x.l/S?l<x.l:r<x.r;
   }
} qq[N];

struct FenwickTree{
   int n;
   vector<int> t;
   void init(int _n){
      n=_n;
      t.assign(n+1, 0);
   }
   void update(int pos, int val){
      for (int i=pos; i<=n; i+=i&(-i)) t[i]+=val;
   }
   int get(int pos){
      int ans=0;
      for (int i=pos; i; i-=i&(-i)) ans+=t[i];
      return ans;
   }
   int lower_bound(int val){
      int ans=0;
      for (int i=16; i>=0; --i) if (ans+(1<<i)<=n && t[ans+(1<<i)]<val){
         ans+=1<<i;
         val-=t[ans];
      }
      return ans+1;
   }
};

int n, m, q, a[N], tdfs, tin[N], tout[N], dep[N], ans[N], cnt[N], tour[N];
int tin2[N], tout2[N], tdfs2;
pair<int, int> st[N*2][LG];
vector<int> g[N];

void dfs(int u, int p){
   tin[u]=++tdfs;
   tin2[u]=++tdfs2;
   tour[tdfs2]=u;
   dep[u]=dep[p]+1;
   st[tdfs][0]={dep[u], u};
   for (int v:g[u]) if (v!=p){
      dfs(v, u);
      ++tdfs;
      st[tdfs][0]={dep[u], u};
   }
   tout[u]=tdfs;
   tout2[u]=tdfs2;
}

void build(){
   for (int k=1; k<LG; ++k) for (int i=1; i+(1<<k)-1<=tdfs; ++i) st[i][k]=min(st[i][k-1], st[i+(1<<(k-1))][k-1]);
}

int lca(int u, int v){
   u=tin[u]; v=tin[v];
   if (u>v) swap(u, v);
   int lg=__lg(v-u+1);
   return min(st[u][lg], st[v-(1<<lg)+1][lg]).second;
}

int distance(int u, int v){
   return dep[u]+dep[v]-dep[lca(u, v)]*2;
}

namespace among{
   struct SUS{
      int cnt[N], prev_arr[N], next_arr[N];
      int size;
      FenwickTree bit;
      int ans;
      int get_order(int x){
         return bit.get(x);
      }
      int find_by_order(int i){
         return bit.lower_bound(i);
      }
      int find_first(){
         return bit.lower_bound(1);
      }
      int find_last(){
         return bit.lower_bound(size);
      }
      void insert(int x){
         if (cnt[x]) return;
         if (size){
            int i=get_order(x);
            int prev=i?find_by_order(i):find_last();
            int next=next_arr[prev];
            ans-=distance(tour[prev], tour[next]);
            ans+=distance(tour[prev], tour[x]);
            ans+=distance(tour[x], tour[next]);
            prev_arr[x]=prev; next_arr[prev]=x;
            prev_arr[next]=x; next_arr[x]=next;
         }
         ++cnt[x];
         bit.update(x, 1);
         if (!size){
            prev_arr[x]=x;
            next_arr[x]=x;
         }
         ++size;
      }
      void erase(int x){
         bit.update(x, -1);
         --size;
         --cnt[x];
         if (size){
            int prev=prev_arr[x];
            int next=next_arr[x];
            ans+=distance(tour[prev], tour[next]);
            ans-=distance(tour[prev], tour[x]);
            ans-=distance(tour[x], tour[next]);
            prev_arr[next]=prev; next_arr[prev]=next;
         }
      }
   } us;
}

void solve(){
   #ifdef sus
   freopen("03-04.txt", "r", stdin);
   freopen("cf.out", "w", stdout);
   #endif
   cin >> n >> m >> q;
   for (int i=1; i<n; ++i){
      int x, y; cin >> x >> y;
      g[x].push_back(y);
      g[y].push_back(x);
   }
   dfs(1, 0);
   build();
   for (int i=1; i<=m; ++i) cin >> a[i];
   for (int i=1; i<=q; ++i){
      int x, y; cin >> x >> y;
      qq[i]={x, y, i};
   }
   sort(qq+1, qq+q+1);
   int cl=1, cr=0;
   among::us.bit.init(n*2);
   for (int i=1; i<=q; ++i){
      int l=qq[i].l, r=qq[i].r;
      while (l<cl){
         --cl;
         among::us.insert(tin2[a[cl]]);
      }
      while (r>cr){
         ++cr;
         among::us.insert(tin2[a[cr]]);
      }
      while (l>cl){
         among::us.erase(tin2[a[cl]]);
         ++cl;
      }
      while (r<cr){
         among::us.erase(tin2[a[cr]]);
         --cr;
      }
      ans[qq[i].i]=among::us.ans/2+1;
   }
   for (int i=1; i<=q; ++i) cout << ans[i] << '\n';
}

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int ntests=1;
   // cin >> ntests;
   for (int i=1; i<=ntests; ++i) solve();
   return 0;
}

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Incorrect 2 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Incorrect 2 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5720 KB Output is correct
3 Correct 6 ms 5724 KB Output is correct
4 Incorrect 1667 ms 31572 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5724 KB Output is correct
2 Runtime error 71 ms 51612 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #5
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5720 KB Output is correct
2 Correct 3 ms 5724 KB Output is correct
3 Correct 6 ms 5720 KB Output is correct
4 Runtime error 2045 ms 53272 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5720 KB Output is correct
2 Correct 2 ms 5724 KB Output is correct
3 Incorrect 2 ms 5724 KB Output isn't correct
4 Halted 0 ms 0 KB -