oj.uz

Submission #985997

# Submission time Handle Problem Language Result Execution time Memory
985997 2024-05-19T14:54:46 Z cig32 Tourism (JOI23_tourism) C++17
10 / 100
 5000 ms 56528 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;
  }
  int supp[2010];
  void resize(int n_, int m_) {
    for(int i=0; i<=n; i++) supp[i] = 0;
    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) {
    for(int i=l; i<=r; i++) supp[i] = 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]
    int ans = 0;
    for(int i=1; i<=m; i++) ans += (supp[i] >= l && supp[i] <= 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(dep[u] >= dep[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(dep[v] >= dep[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: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:225: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]
  225 |   for(int i=0; i<euler.size(); i++) {
      |                ~^~~~~~~~~~~~~
tourism.cpp:229: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]
  229 |     for(int j=0; j+(1<<i)-1<euler.size(); j++) {
      |                  ~~~~~~~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23644 KB Output is correct
2 Correct 4 ms 23652 KB Output is correct
3 Correct 4 ms 23644 KB Output is correct
4 Correct 6 ms 29956 KB Output is correct
5 Correct 5 ms 29788 KB Output is correct
6 Correct 5 ms 29788 KB Output is correct
7 Correct 5 ms 29788 KB Output is correct
8 Correct 5 ms 31832 KB Output is correct
9 Correct 5 ms 31836 KB Output is correct
10 Correct 6 ms 32004 KB Output is correct
11 Correct 5 ms 31836 KB Output is correct
12 Correct 6 ms 31836 KB Output is correct
13 Correct 5 ms 31836 KB Output is correct
14 Correct 5 ms 32088 KB Output is correct
15 Correct 5 ms 31836 KB Output is correct
16 Correct 5 ms 31836 KB Output is correct
17 Correct 5 ms 31836 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 5 ms 31836 KB Output is correct
20 Correct 6 ms 31836 KB Output is correct
21 Correct 5 ms 31928 KB Output is correct
22 Correct 5 ms 31836 KB Output is correct
23 Correct 5 ms 31836 KB Output is correct
24 Correct 5 ms 31832 KB Output is correct
25 Correct 5 ms 31836 KB Output is correct
26 Correct 5 ms 31980 KB Output is correct
27 Correct 3 ms 17500 KB Output is correct
28 Correct 5 ms 31836 KB Output is correct
29 Correct 6 ms 31836 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23644 KB Output is correct
2 Correct 4 ms 23652 KB Output is correct
3 Correct 4 ms 23644 KB Output is correct
4 Correct 6 ms 29956 KB Output is correct
5 Correct 5 ms 29788 KB Output is correct
6 Correct 5 ms 29788 KB Output is correct
7 Correct 5 ms 29788 KB Output is correct
8 Correct 5 ms 31832 KB Output is correct
9 Correct 5 ms 31836 KB Output is correct
10 Correct 6 ms 32004 KB Output is correct
11 Correct 5 ms 31836 KB Output is correct
12 Correct 6 ms 31836 KB Output is correct
13 Correct 5 ms 31836 KB Output is correct
14 Correct 5 ms 32088 KB Output is correct
15 Correct 5 ms 31836 KB Output is correct
16 Correct 5 ms 31836 KB Output is correct
17 Correct 5 ms 31836 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 5 ms 31836 KB Output is correct
20 Correct 6 ms 31836 KB Output is correct
21 Correct 5 ms 31928 KB Output is correct
22 Correct 5 ms 31836 KB Output is correct
23 Correct 5 ms 31836 KB Output is correct
24 Correct 5 ms 31832 KB Output is correct
25 Correct 5 ms 31836 KB Output is correct
26 Correct 5 ms 31980 KB Output is correct
27 Correct 3 ms 17500 KB Output is correct
28 Correct 5 ms 31836 KB Output is correct
29 Correct 6 ms 31836 KB Output is correct
30 Correct 12 ms 36188 KB Output is correct
31 Correct 11 ms 36188 KB Output is correct
32 Correct 16 ms 36444 KB Output is correct
33 Correct 12 ms 36444 KB Output is correct
34 Correct 13 ms 36444 KB Output is correct
35 Correct 12 ms 36444 KB Output is correct
36 Correct 13 ms 36320 KB Output is correct
37 Correct 12 ms 36600 KB Output is correct
38 Correct 9 ms 36444 KB Output is correct
39 Correct 11 ms 36444 KB Output is correct
40 Correct 9 ms 36404 KB Output is correct
41 Correct 8 ms 36444 KB Output is correct
42 Correct 9 ms 36476 KB Output is correct
43 Correct 8 ms 36444 KB Output is correct
44 Correct 10 ms 36168 KB Output is correct
45 Correct 10 ms 36184 KB Output is correct
46 Correct 10 ms 36188 KB Output is correct
47 Correct 10 ms 36184 KB Output is correct
48 Correct 10 ms 36184 KB Output is correct
49 Correct 9 ms 36364 KB Output is correct
50 Correct 9 ms 36444 KB Output is correct
51 Correct 9 ms 36344 KB Output is correct
52 Correct 10 ms 36448 KB Output is correct
53 Correct 9 ms 36444 KB Output is correct
54 Correct 11 ms 36292 KB Output is correct
55 Correct 9 ms 36452 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 6 ms 36292 KB Output is correct
58 Correct 13 ms 40280 KB Output is correct

Subtask #3
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 5 ms 17532 KB Output is correct
4 Execution timed out 5037 ms 56528 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 23644 KB Output is correct
2 Execution timed out 5075 ms 48768 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
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 Execution timed out 5058 ms 53952 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #6
0 / 41.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23644 KB Output is correct
2 Correct 4 ms 23652 KB Output is correct
3 Correct 4 ms 23644 KB Output is correct
4 Correct 6 ms 29956 KB Output is correct
5 Correct 5 ms 29788 KB Output is correct
6 Correct 5 ms 29788 KB Output is correct
7 Correct 5 ms 29788 KB Output is correct
8 Correct 5 ms 31832 KB Output is correct
9 Correct 5 ms 31836 KB Output is correct
10 Correct 6 ms 32004 KB Output is correct
11 Correct 5 ms 31836 KB Output is correct
12 Correct 6 ms 31836 KB Output is correct
13 Correct 5 ms 31836 KB Output is correct
14 Correct 5 ms 32088 KB Output is correct
15 Correct 5 ms 31836 KB Output is correct
16 Correct 5 ms 31836 KB Output is correct
17 Correct 5 ms 31836 KB Output is correct
18 Correct 5 ms 33884 KB Output is correct
19 Correct 5 ms 31836 KB Output is correct
20 Correct 6 ms 31836 KB Output is correct
21 Correct 5 ms 31928 KB Output is correct
22 Correct 5 ms 31836 KB Output is correct
23 Correct 5 ms 31836 KB Output is correct
24 Correct 5 ms 31832 KB Output is correct
25 Correct 5 ms 31836 KB Output is correct
26 Correct 5 ms 31980 KB Output is correct
27 Correct 3 ms 17500 KB Output is correct
28 Correct 5 ms 31836 KB Output is correct
29 Correct 6 ms 31836 KB Output is correct
30 Correct 12 ms 36188 KB Output is correct
31 Correct 11 ms 36188 KB Output is correct
32 Correct 16 ms 36444 KB Output is correct
33 Correct 12 ms 36444 KB Output is correct
34 Correct 13 ms 36444 KB Output is correct
35 Correct 12 ms 36444 KB Output is correct
36 Correct 13 ms 36320 KB Output is correct
37 Correct 12 ms 36600 KB Output is correct
38 Correct 9 ms 36444 KB Output is correct
39 Correct 11 ms 36444 KB Output is correct
40 Correct 9 ms 36404 KB Output is correct
41 Correct 8 ms 36444 KB Output is correct
42 Correct 9 ms 36476 KB Output is correct
43 Correct 8 ms 36444 KB Output is correct
44 Correct 10 ms 36168 KB Output is correct
45 Correct 10 ms 36184 KB Output is correct
46 Correct 10 ms 36188 KB Output is correct
47 Correct 10 ms 36184 KB Output is correct
48 Correct 10 ms 36184 KB Output is correct
49 Correct 9 ms 36364 KB Output is correct
50 Correct 9 ms 36444 KB Output is correct
51 Correct 9 ms 36344 KB Output is correct
52 Correct 10 ms 36448 KB Output is correct
53 Correct 9 ms 36444 KB Output is correct
54 Correct 11 ms 36292 KB Output is correct
55 Correct 9 ms 36452 KB Output is correct
56 Correct 4 ms 17500 KB Output is correct
57 Correct 6 ms 36292 KB Output is correct
58 Correct 13 ms 40280 KB Output is correct
59 Correct 4 ms 23644 KB Output is correct
60 Correct 3 ms 17500 KB Output is correct
61 Correct 5 ms 17532 KB Output is correct
62 Execution timed out 5037 ms 56528 KB Time limit exceeded
63 Halted 0 ms 0 KB -