oj.uz

Submission #1092036

# Submission time Handle Problem Language Result Execution time Memory
1092036 2024-09-23T02:23:08 Z juicy Birthday gift (IZhO18_treearray) C++17
0 / 100
 12 ms 24156 KB 
#include <bits/stdc++.h>

using namespace std;

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

const int N = 2e5 + 5, LG = 19;

int n, m, q;
int a[N], tin[N], tout[N], lg[2 * N], spt[LG][2 * N];
set<int> x[N], y[N];
vector<int> g[N];

int cmb(int u, int v) {
  return tin[u] < tin[v] ? u : v;
}

int lca(int u, int v) {
  int l = min(tin[u], tin[v]), r = max(tin[u], tin[v]);
  int k = lg[r - l + 1];
  return cmb(spt[k][l], spt[k][r - (1 << k) + 1]);
}

int timer;

void dfs(int u) {
  spt[0][tin[u] = ++timer] = u;
  for (int v : g[u]) {
    if (!tin[v]) {
      dfs(v);
      spt[0][++timer] = u;
    }
  }
  tout[u] = timer;
}

int main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);
  
  cin >> n >> m >> q;
  for (int i = 1; i < n; ++i) {
    int u, v; cin >> u >> v;
    g[u].push_back(v);
    g[v].push_back(u);
  }
  dfs(1);
  for (int i = 2; i <= timer; ++i) {
    lg[i] = lg[i / 2] + 1;
  }
  for (int j = 1; j < LG; ++j) {
    for (int i = 1; i + (1 << j) - 1 <= timer; ++i) {
      spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    x[i].insert(n + 1);
    y[i].insert(n + 1);
  }
  for (int i = 1; i <= m; ++i) {
    cin >> a[i];
  }
  for (int i = 1; i <= m; ++i) {
    x[a[i]].insert(i);
    if (i < m) {
      y[lca(a[i], a[i + 1])].insert(i);
    }
  }
  while (q--) {
    int t; cin >> t;
    if (t == 1) {
      int i, v; cin >> i >> v;
      x[a[i]].erase(i);
      if (i > 1) {
        y[lca(a[i - 1], a[i])].erase(i - 1);
      }
      if (i < m) {
        y[lca(a[i], a[i + 1])].erase(i);
      }
      a[i] = v;
      x[a[i]].insert(i);
      if (i > 1) {
        y[lca(a[i - 1], a[i])].insert(i - 1);
      }
      if (i < m) {
        y[lca(a[i], a[i + 1])].insert(i);
      }
    } else {
      int l, r, v; cin >> l >> r >> v;
      int a = *x[v].lower_bound(l), b = *y[v].lower_bound(l);
      if (a <= r) {
        cout << a << " " << a << "\n";
      } else if (b < r) {
        cout << b << " " << b + 1 << "\n";
      } else {
        cout << "-1 -1\n";
      }
    }
  }
  return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:56:61: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   56 |       spt[j][i] = cmb(spt[j - 1][i], spt[j - 1][i + (1 << j - 1)]);
      |                                                           ~~^~~

Subtask #1
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23944 KB n=100
3 Correct 9 ms 23900 KB n=100
4 Correct 9 ms 23896 KB n=100
5 Correct 9 ms 23896 KB n=100
6 Correct 10 ms 23900 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23896 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23900 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 9 ms 23900 KB n=100
14 Correct 9 ms 23900 KB n=100
15 Correct 10 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 10 ms 23896 KB n=100
18 Correct 9 ms 23900 KB n=100
19 Correct 12 ms 23908 KB n=100
20 Correct 10 ms 23912 KB n=100
21 Correct 9 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 24156 KB n=100
24 Correct 9 ms 23896 KB n=100
25 Correct 10 ms 23900 KB n=100
26 Incorrect 11 ms 23900 KB Wrong output format.
27 Halted 0 ms 0 KB -

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23944 KB n=100
3 Correct 9 ms 23900 KB n=100
4 Correct 9 ms 23896 KB n=100
5 Correct 9 ms 23896 KB n=100
6 Correct 10 ms 23900 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23896 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23900 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 9 ms 23900 KB n=100
14 Correct 9 ms 23900 KB n=100
15 Correct 10 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 10 ms 23896 KB n=100
18 Correct 9 ms 23900 KB n=100
19 Correct 12 ms 23908 KB n=100
20 Correct 10 ms 23912 KB n=100
21 Correct 9 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 24156 KB n=100
24 Correct 9 ms 23896 KB n=100
25 Correct 10 ms 23900 KB n=100
26 Incorrect 11 ms 23900 KB Wrong output format.
27 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23944 KB n=100
3 Correct 9 ms 23900 KB n=100
4 Correct 9 ms 23896 KB n=100
5 Correct 9 ms 23896 KB n=100
6 Correct 10 ms 23900 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23896 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23900 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 9 ms 23900 KB n=100
14 Correct 9 ms 23900 KB n=100
15 Correct 10 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 10 ms 23896 KB n=100
18 Correct 9 ms 23900 KB n=100
19 Correct 12 ms 23908 KB n=100
20 Correct 10 ms 23912 KB n=100
21 Correct 9 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 24156 KB n=100
24 Correct 9 ms 23896 KB n=100
25 Correct 10 ms 23900 KB n=100
26 Incorrect 11 ms 23900 KB Wrong output format.
27 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 23900 KB n=5
2 Correct 11 ms 23944 KB n=100
3 Correct 9 ms 23900 KB n=100
4 Correct 9 ms 23896 KB n=100
5 Correct 9 ms 23896 KB n=100
6 Correct 10 ms 23900 KB n=100
7 Correct 10 ms 23900 KB n=100
8 Correct 10 ms 23900 KB n=100
9 Correct 10 ms 23896 KB n=100
10 Correct 10 ms 23900 KB n=100
11 Correct 10 ms 23900 KB n=100
12 Correct 10 ms 23900 KB n=100
13 Correct 9 ms 23900 KB n=100
14 Correct 9 ms 23900 KB n=100
15 Correct 10 ms 23896 KB n=100
16 Correct 10 ms 23900 KB n=100
17 Correct 10 ms 23896 KB n=100
18 Correct 9 ms 23900 KB n=100
19 Correct 12 ms 23908 KB n=100
20 Correct 10 ms 23912 KB n=100
21 Correct 9 ms 23900 KB n=100
22 Correct 10 ms 23900 KB n=100
23 Correct 11 ms 24156 KB n=100
24 Correct 9 ms 23896 KB n=100
25 Correct 10 ms 23900 KB n=100
26 Incorrect 11 ms 23900 KB Wrong output format.
27 Halted 0 ms 0 KB -