oj.uz

Submission #985993

# Submission time Handle Problem Language Result Execution time Memory
985993 2024-05-19T14:46:37 Z cig32 Tourism (JOI23_tourism) C++17
31 / 100
 1038 ms 65280 KB 
#include "bits/stdc++.h"
using namespace std;
#define int long long
#define double long double
const int MAXN = 2e5 + 10;
const int MOD = 1e9 + 7;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
int bm(int b, int p) {
  if(p==0) return 1 % MOD;
  int r = bm(b, p >> 1);
  if(p&1) return (((r*r) % MOD) * b) % MOD;
  return (r*r) % MOD;
}
int inv(int b) { 
  return bm(b, MOD-2);
}
int fastlog(int x) {
  return (x == 0 ? -1 : 64 - __builtin_clzll(x) - 1);
}
void printcase(int i) { cout << "Case #" << i << ": "; }
static void run_with_stack_size(void (*func)(void), size_t stsize) {
  char *stack, *send;
  stack = (char *)malloc(stsize);
  send = stack + stsize - 16;
  send = (char *)((uintptr_t)send / 16 * 16);
  asm volatile(
    "mov %%rsp, (%0)\n"
    "mov %0, %%rsp\n"
    :
    : "r"(send));
  func();
  asm volatile("mov (%0), %%rsp\n" : : "r"(send));
  free(stack);
}
vector<int> adj[MAXN];
pair<pair<int,int>,int> qry[MAXN];
bool cmp(pair<pair<int,int>,int> x,pair<pair<int,int>,int>y) {
  return x.first.second<y.first.second;
}
struct sets_and_fenwick {
  int n, m; // n = ARRAY SIZE, m = MAX ELEMENT
  vector<int> bit;
  set< pair<pair<int,int>,int> > st;
  const int base = 1;
  const int oob = -1;
  void add(int x, int v) {
    x++;
    for(;x<m+5;x+=x&-x) bit[x] += v;
  }
  int sum(int x) {
    x++;
    int s = 0;
    for(;x;x-=x&-x) s+=bit[x];
    return s;
  }
  void resize(int n_, int m_) {
    m = m_;
    n = n_;
    bit.resize(m + 5);
    st.insert({{base, n - 1 + base}, 0});
    st.insert({{n + base, n + base}, oob});
    add(0, n);
  }
  void reset() {
    for(int i=0; i<=m; i++) bit[i] = 0;
    st.clear();
    st.insert({{base, n - 1 + base}, 0});
    st.insert({{n + base, n + base}, oob});
    add(0, n);
  }
  void update_range(int l, int r, int v) {
    vector<pair<pair<int,int>,int> > rem,ins;
    ins.push_back({{l, r}, v});
    auto it = st.lower_bound({{l, 0}, 0});
    while(1) {
      int lb = (*it).first.first;
      int rb = (*it).first.second;
      int val = (*it).second;
      if(lb == n+base) break;
      if(lb <= r) {
        if(rb <= r) {
          rem.push_back(*it);
          it++;
          continue;
        }
        rem.push_back(*it);
        ins.push_back({{r + 1, rb}, val});
        break;
      }
      else break;
    }
    it = st.lower_bound({{l, 0}, 0});
    if((*it).first.first > base) {
      it--;
      int lb = (*it).first.first;
      int rb = (*it).first.second;
      int val = (*it).second;
      if(rb >= l) {
        if(rb > r) {
          rem.push_back(*it);
          ins.push_back({{lb, l - 1}, val});
          ins.push_back({{r + 1, rb}, val});
        }
        else {
          rem.push_back(*it);
          ins.push_back({{lb, l - 1}, val});
        }
      }
    }
    for(auto x: rem) {
      st.erase(x);
      add(x.second, -(x.first.second - x.first.first + 1));
    }
    for(auto x: ins) {
      st.insert(x);
      add(x.second, x.first.second - x.first.first + 1);
    }
  }
  int query_ranges() { // Number of disjoint ranges 
    return st.size(); 
  }
  int query_count(int l, int r) { // Number of elements having value in [l, r]
    return sum(r) - sum(l - 1);
  }
};

int sz[MAXN];
void dfs1(int node, int prv) {
  sz[node] = 1;
  for(int x: adj[node]) {
    if(x != prv) {
      dfs1(x, node);
      sz[node] += sz[x];
    }
  }
}
bool hld(int x, int y) {
  return sz[x] > sz[y];
}
int L[MAXN], R[MAXN];
pair<int32_t,int32_t> st[18][MAXN];
vector<int> euler;
int ord[MAXN];
int ptr;
int dep[MAXN];
int par[MAXN];
int pos[MAXN];
int dage[MAXN]; // pos to pos
void dfs2(int node, int prv) {
  ord[++ptr] = node;
  par[node] = prv;
  pos[node] = ptr;
  euler.push_back(node);
  dep[node] = (prv == -1 ? 0 : dep[prv] + 1);
  for(int x: adj[node]) {
    if(x != prv) {
      dfs2(x, node);
      euler.push_back(node);
    }
  }
}
int lca(int x, int y) {
  int m1 = min(L[x], L[y]);
  int m2 = max(R[x], R[y]);
  int k = 32 - __builtin_clz(m2 - m1 + 1) - 1;
  return min(st[k][m1], st[k][m2 - (1<<k) + 1]).second;
}
sets_and_fenwick saf;
void complete_path(int u, int v, int w) {
  int l = lca(u, v);
  while(u != l) {
    int p1 = pos[u], p2 = dage[p1];
    if(p2 <= pos[l]) p2 = pos[l];
    swap(p1, p2);
    int tp = ord[p1]; // range [p1, p2]
    saf.update_range(p1, p2, w);
    if(tp == l) break;
    u = par[tp];
  }
  while(v != l) {
    int p1 = pos[v], p2 = dage[p1];
    if(p2 <= pos[l]) p2 = pos[l];
    swap(p1, p2);
    int tp = ord[p1]; // range [p1, p2]
    saf.update_range(p1, p2, w);
    if(tp == l) break;
    v = par[tp];
  }
}
void solve(int tc) {
  int n, m, q;
  cin >> n >> m >> q;
  saf.resize(n, m);
  for(int i=1; i<n; i++) {
    int x, y;
    cin >> x >> y;
    adj[x].push_back(y);
    adj[y].push_back(x);
  }
  int c[m+1];
  for(int i=1; i<=m; i++) cin >> c[i];
  for(int i=1; i<=q; i++) {
    cin >> qry[i].first.first >> qry[i].first.second;
    qry[i].second = i;
  }
  sort(qry + 1, qry + q + 1, cmp);
  dfs1(1, -1);
  for(int i=1; i<=n; i++) sort(adj[i].begin(), adj[i].end(), hld);
  dfs2(1, -1);
  for(int i=0; i<euler.size(); i++) {
    R[euler[i]] = i;
  }
  for(int i=euler.size()-1; i>=0; i--) {
    L[euler[i]] = i;
  }
  for(int i=0; i<euler.size(); i++) {
    st[0][i] = {dep[euler[i]], euler[i]};
  }
  for(int i=1; i<18; i++) {
    for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      st[i][j] = min(st[i-1][j], st[i-1][j+(1<<(i-1))]);
    }
  }
  dage[1] = 1;
  for(int i=2; i<=n; i++) {
    if(dep[ord[i]] > dep[ord[i-1]]) dage[i] = dage[i-1];
    else dage[i] = i;
  }
  int ans[q+1];
  int maxr = 1;
  saf.update_range(pos[c[1]], pos[c[1]], 1);
  for(int i=1; i<=q; i++) {
    bool yes = 0;
    int rb = qry[i].first.second;
    while(maxr < rb) {
      yes = 1;
      complete_path(c[maxr], c[maxr + 1], maxr);
      maxr++;
    }
    if(yes) {
      saf.update_range(pos[c[rb]], pos[c[rb]], rb);
    }
    ans[qry[i].second] = saf.query_count(qry[i].first.first, rb);
  }
  for(int i=1; i<=q;i++) cout<<ans[i]<<"\n";
} 
void uwu() {
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
}
int32_t main() {
  #ifdef ONLINE_JUDGE
  uwu();
  #endif
  #ifndef ONLINE_JUDGE
  run_with_stack_size(uwu, 1024 * 1024 * 1024); // run with a 1 GiB stack
  #endif
}
/*
g++ B.cpp -std=c++17 -O2 -o B
./B < input.txt

0 1 2 5 
3 7 11 6 
15 14 13 10 
12 8 4 9 

*/

Compilation message

tourism.cpp: In function 'void solve(long long int)':
tourism.cpp:213:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  213 |   for(int i=0; i<euler.size(); i++) {
      |                ~^~~~~~~~~~~~~
tourism.cpp:219:17: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  219 |   for(int i=0; i<euler.size(); i++) {
      |                ~^~~~~~~~~~~~~
tourism.cpp:223:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  223 |     for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 5.0

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

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23644 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 4 ms 17600 KB Output is correct
4 Correct 126 ms 57040 KB Output is correct
5 Correct 98 ms 60728 KB Output is correct
6 Correct 117 ms 61892 KB Output is correct
7 Correct 156 ms 64172 KB Output is correct
8 Correct 151 ms 65128 KB Output is correct
9 Correct 154 ms 64960 KB Output is correct
10 Correct 155 ms 63588 KB Output is correct
11 Correct 152 ms 63940 KB Output is correct
12 Correct 141 ms 64636 KB Output is correct
13 Correct 130 ms 64564 KB Output is correct
14 Correct 128 ms 63964 KB Output is correct
15 Correct 54 ms 62088 KB Output is correct
16 Correct 154 ms 64604 KB Output is correct
17 Correct 45 ms 24296 KB Output is correct

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23640 KB Output is correct
2 Correct 294 ms 52456 KB Output is correct
3 Correct 482 ms 54116 KB Output is correct
4 Correct 363 ms 53704 KB Output is correct
5 Correct 644 ms 59752 KB Output is correct
6 Correct 595 ms 59588 KB Output is correct
7 Correct 584 ms 58048 KB Output is correct
8 Correct 583 ms 59392 KB Output is correct
9 Correct 612 ms 59836 KB Output is correct
10 Correct 596 ms 59332 KB Output is correct
11 Correct 588 ms 60284 KB Output is correct
12 Correct 639 ms 58068 KB Output is correct
13 Incorrect 600 ms 58308 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #5
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23640 KB Output is correct
2 Correct 3 ms 17500 KB Output is correct
3 Correct 4 ms 17500 KB Output is correct
4 Correct 788 ms 57824 KB Output is correct
5 Correct 816 ms 58364 KB Output is correct
6 Correct 955 ms 63124 KB Output is correct
7 Correct 1006 ms 63492 KB Output is correct
8 Correct 1038 ms 63936 KB Output is correct
9 Correct 1020 ms 63992 KB Output is correct
10 Correct 1012 ms 65244 KB Output is correct
11 Correct 1000 ms 63864 KB Output is correct
12 Correct 1016 ms 65108 KB Output is correct
13 Correct 1014 ms 65280 KB Output is correct
14 Correct 44 ms 24656 KB Output is correct

Subtask #6
0 / 41.0

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