oj.uz

Submission #637996

# Submission time Handle Problem Language Result Execution time Memory
637996 2022-09-04T06:43:30 Z tvladm2009 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1040 ms 84184 KB 
#include <bits/stdc++.h>

const int MAX_N = 2 * 1e5;
const int MAX_L = 19;

std::vector<int> g[MAX_N + 1];
int a[MAX_N + 1], up[MAX_N + 1][MAX_L + 1], l[MAX_N + 1], r[MAX_N + 1];
std::set<int> one[MAX_N + 1], two[MAX_N + 1];
int t = 0;

void dfs(int u, int p) {
  up[u][0] = p;
  for (int i = 1; i <= MAX_L; i++) {
    up[u][i] = up[up[u][i - 1]][i - 1];
  }
  l[u] = ++t;
  for (int v : g[u]) {
    if (v != p) {
      dfs(v, u);
    }
  }
  r[u] = ++t;
}

bool is_ancestor(int u, int v) {
  return l[u] <= l[v] && r[v] <= r[u];
}

int lca(int u, int v) {
  if (is_ancestor(u, v)) {
    return v;
  } else if (is_ancestor(v, u)) {
    return u;
  }
  for (int i = MAX_L; i >= 0; i--) {
    if (!is_ancestor(up[u][i], v)) {
      u = up[u][i];
    }
  }
  return up[u][0];
}

int main() {
  std::ios_base::sync_with_stdio(0);
  std::cin.tie(0);
  int n, m, q;
  std::cin >> n >> m >> q;
  for (int i = 1; i <= n - 1; i++) {
    int x, y;
    std::cin >> x >> y;
    g[x].push_back(y);
    g[y].push_back(x);
  }
  dfs(1, 1);
  for (int i = 1; i <= m; i++) {
    std::cin >> a[i];
    one[a[i]].insert(i);
    if (i > 1) {
      two[lca(a[i - 1], a[i])].insert(i - 1);
    }
  }
  for (int i = 1; i <= q; i++) {
    int type = 0;
    std::cin >> type;
    if (type == 1) {
      int pos, v;
      std::cin >> pos >> v;
      one[a[pos]].erase(pos);
      if (pos > 1) {
        two[lca(a[pos - 1], a[pos])].erase(pos - 1);
      }
      if (pos < m) {
        two[lca(a[pos], a[pos + 1])].erase(pos);
      }
      a[pos] = v;
      one[a[pos]].insert(pos);
      if (pos > 1) {
        two[lca(a[pos - 1], a[pos])].insert(pos - 1);
      }
      if (pos < m) {
        two[lca(a[pos], a[pos + 1])].insert(pos);
      }
    } else {
      int l, r, v;
      std::cin >> l >> r >> v;
      auto it = one[v].lower_bound(l);
      if (it != one[v].end() && (*it) <= r) {
        std::cout << (*it) << " " << (*it) << "\n";
        continue;
      }
      it = two[v].lower_bound(l);
      if (it != two[v].end() && (*it) + 1 <= r) {
        std::cout << (*it) << " " << (*it) + 1 << "\n";
        continue;
      }
      std::cout << "-1 -1\n";
    }
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23788 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 12 ms 23816 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23816 KB n=100
6 Correct 12 ms 23816 KB n=100
7 Correct 13 ms 23764 KB n=100
8 Correct 15 ms 23764 KB n=100
9 Correct 13 ms 23760 KB n=100
10 Correct 12 ms 23832 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23820 KB n=100
18 Correct 13 ms 23820 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 12 ms 23792 KB n=100
21 Correct 12 ms 23808 KB n=100
22 Correct 11 ms 23764 KB n=100
23 Correct 12 ms 23816 KB n=100
24 Correct 12 ms 23816 KB n=100
25 Correct 12 ms 23820 KB n=100
26 Correct 15 ms 23716 KB n=12
27 Correct 12 ms 23820 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23788 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 12 ms 23816 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23816 KB n=100
6 Correct 12 ms 23816 KB n=100
7 Correct 13 ms 23764 KB n=100
8 Correct 15 ms 23764 KB n=100
9 Correct 13 ms 23760 KB n=100
10 Correct 12 ms 23832 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23820 KB n=100
18 Correct 13 ms 23820 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 12 ms 23792 KB n=100
21 Correct 12 ms 23808 KB n=100
22 Correct 11 ms 23764 KB n=100
23 Correct 12 ms 23816 KB n=100
24 Correct 12 ms 23816 KB n=100
25 Correct 12 ms 23820 KB n=100
26 Correct 15 ms 23716 KB n=12
27 Correct 12 ms 23820 KB n=100
28 Correct 13 ms 23948 KB n=500
29 Correct 12 ms 23940 KB n=500
30 Correct 17 ms 23892 KB n=500
31 Correct 12 ms 23892 KB n=500
32 Correct 12 ms 23892 KB n=500
33 Correct 13 ms 23920 KB n=500
34 Correct 15 ms 23916 KB n=500
35 Correct 12 ms 23892 KB n=500
36 Correct 15 ms 23924 KB n=500
37 Correct 12 ms 23900 KB n=500
38 Correct 12 ms 23892 KB n=500
39 Correct 13 ms 23864 KB n=500
40 Correct 12 ms 23844 KB n=500
41 Correct 15 ms 23892 KB n=500
42 Correct 13 ms 23868 KB n=500
43 Correct 14 ms 24032 KB n=500
44 Correct 14 ms 23856 KB n=500
45 Correct 13 ms 23892 KB n=500
46 Correct 12 ms 23892 KB n=500
47 Correct 13 ms 23948 KB n=500
48 Correct 12 ms 23868 KB n=500
49 Correct 13 ms 23952 KB n=500
50 Correct 16 ms 23948 KB n=500
51 Correct 14 ms 23924 KB n=500
52 Correct 13 ms 23956 KB n=500
53 Correct 13 ms 24020 KB n=500
54 Correct 12 ms 23952 KB n=500
55 Correct 13 ms 23796 KB n=278
56 Correct 12 ms 23892 KB n=500
57 Correct 12 ms 23892 KB n=500
58 Correct 12 ms 23892 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23788 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 12 ms 23816 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23816 KB n=100
6 Correct 12 ms 23816 KB n=100
7 Correct 13 ms 23764 KB n=100
8 Correct 15 ms 23764 KB n=100
9 Correct 13 ms 23760 KB n=100
10 Correct 12 ms 23832 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23820 KB n=100
18 Correct 13 ms 23820 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 12 ms 23792 KB n=100
21 Correct 12 ms 23808 KB n=100
22 Correct 11 ms 23764 KB n=100
23 Correct 12 ms 23816 KB n=100
24 Correct 12 ms 23816 KB n=100
25 Correct 12 ms 23820 KB n=100
26 Correct 15 ms 23716 KB n=12
27 Correct 12 ms 23820 KB n=100
28 Correct 13 ms 23948 KB n=500
29 Correct 12 ms 23940 KB n=500
30 Correct 17 ms 23892 KB n=500
31 Correct 12 ms 23892 KB n=500
32 Correct 12 ms 23892 KB n=500
33 Correct 13 ms 23920 KB n=500
34 Correct 15 ms 23916 KB n=500
35 Correct 12 ms 23892 KB n=500
36 Correct 15 ms 23924 KB n=500
37 Correct 12 ms 23900 KB n=500
38 Correct 12 ms 23892 KB n=500
39 Correct 13 ms 23864 KB n=500
40 Correct 12 ms 23844 KB n=500
41 Correct 15 ms 23892 KB n=500
42 Correct 13 ms 23868 KB n=500
43 Correct 14 ms 24032 KB n=500
44 Correct 14 ms 23856 KB n=500
45 Correct 13 ms 23892 KB n=500
46 Correct 12 ms 23892 KB n=500
47 Correct 13 ms 23948 KB n=500
48 Correct 12 ms 23868 KB n=500
49 Correct 13 ms 23952 KB n=500
50 Correct 16 ms 23948 KB n=500
51 Correct 14 ms 23924 KB n=500
52 Correct 13 ms 23956 KB n=500
53 Correct 13 ms 24020 KB n=500
54 Correct 12 ms 23952 KB n=500
55 Correct 13 ms 23796 KB n=278
56 Correct 12 ms 23892 KB n=500
57 Correct 12 ms 23892 KB n=500
58 Correct 12 ms 23892 KB n=500
59 Correct 17 ms 24216 KB n=2000
60 Correct 14 ms 24404 KB n=2000
61 Correct 18 ms 24336 KB n=2000
62 Correct 18 ms 24312 KB n=2000
63 Correct 15 ms 24216 KB n=2000
64 Correct 15 ms 24292 KB n=2000
65 Correct 15 ms 24212 KB n=2000
66 Correct 15 ms 24344 KB n=2000
67 Correct 17 ms 24276 KB n=2000
68 Correct 14 ms 24296 KB n=2000
69 Correct 14 ms 24312 KB n=2000
70 Correct 16 ms 24280 KB n=2000
71 Correct 14 ms 24208 KB n=2000
72 Correct 16 ms 24276 KB n=2000
73 Correct 15 ms 24212 KB n=2000
74 Correct 14 ms 24276 KB n=1844
75 Correct 14 ms 24284 KB n=2000
76 Correct 17 ms 24276 KB n=2000
77 Correct 16 ms 24292 KB n=2000
78 Correct 16 ms 24276 KB n=2000
79 Correct 17 ms 24268 KB n=2000
80 Correct 16 ms 24292 KB n=2000
81 Correct 15 ms 24276 KB n=2000
82 Correct 16 ms 24240 KB n=2000
83 Correct 15 ms 24276 KB n=2000
84 Correct 21 ms 24320 KB n=2000
85 Correct 15 ms 24276 KB n=2000
86 Correct 16 ms 24340 KB n=2000
87 Correct 15 ms 24276 KB n=2000
88 Correct 17 ms 24404 KB n=2000
89 Correct 14 ms 24372 KB n=2000
90 Correct 15 ms 24404 KB n=2000
91 Correct 14 ms 24292 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23788 KB n=5
2 Correct 12 ms 23816 KB n=100
3 Correct 12 ms 23816 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 12 ms 23816 KB n=100
6 Correct 12 ms 23816 KB n=100
7 Correct 13 ms 23764 KB n=100
8 Correct 15 ms 23764 KB n=100
9 Correct 13 ms 23760 KB n=100
10 Correct 12 ms 23832 KB n=100
11 Correct 12 ms 23764 KB n=100
12 Correct 12 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 14 ms 23844 KB n=100
17 Correct 13 ms 23820 KB n=100
18 Correct 13 ms 23820 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 12 ms 23792 KB n=100
21 Correct 12 ms 23808 KB n=100
22 Correct 11 ms 23764 KB n=100
23 Correct 12 ms 23816 KB n=100
24 Correct 12 ms 23816 KB n=100
25 Correct 12 ms 23820 KB n=100
26 Correct 15 ms 23716 KB n=12
27 Correct 12 ms 23820 KB n=100
28 Correct 13 ms 23948 KB n=500
29 Correct 12 ms 23940 KB n=500
30 Correct 17 ms 23892 KB n=500
31 Correct 12 ms 23892 KB n=500
32 Correct 12 ms 23892 KB n=500
33 Correct 13 ms 23920 KB n=500
34 Correct 15 ms 23916 KB n=500
35 Correct 12 ms 23892 KB n=500
36 Correct 15 ms 23924 KB n=500
37 Correct 12 ms 23900 KB n=500
38 Correct 12 ms 23892 KB n=500
39 Correct 13 ms 23864 KB n=500
40 Correct 12 ms 23844 KB n=500
41 Correct 15 ms 23892 KB n=500
42 Correct 13 ms 23868 KB n=500
43 Correct 14 ms 24032 KB n=500
44 Correct 14 ms 23856 KB n=500
45 Correct 13 ms 23892 KB n=500
46 Correct 12 ms 23892 KB n=500
47 Correct 13 ms 23948 KB n=500
48 Correct 12 ms 23868 KB n=500
49 Correct 13 ms 23952 KB n=500
50 Correct 16 ms 23948 KB n=500
51 Correct 14 ms 23924 KB n=500
52 Correct 13 ms 23956 KB n=500
53 Correct 13 ms 24020 KB n=500
54 Correct 12 ms 23952 KB n=500
55 Correct 13 ms 23796 KB n=278
56 Correct 12 ms 23892 KB n=500
57 Correct 12 ms 23892 KB n=500
58 Correct 12 ms 23892 KB n=500
59 Correct 17 ms 24216 KB n=2000
60 Correct 14 ms 24404 KB n=2000
61 Correct 18 ms 24336 KB n=2000
62 Correct 18 ms 24312 KB n=2000
63 Correct 15 ms 24216 KB n=2000
64 Correct 15 ms 24292 KB n=2000
65 Correct 15 ms 24212 KB n=2000
66 Correct 15 ms 24344 KB n=2000
67 Correct 17 ms 24276 KB n=2000
68 Correct 14 ms 24296 KB n=2000
69 Correct 14 ms 24312 KB n=2000
70 Correct 16 ms 24280 KB n=2000
71 Correct 14 ms 24208 KB n=2000
72 Correct 16 ms 24276 KB n=2000
73 Correct 15 ms 24212 KB n=2000
74 Correct 14 ms 24276 KB n=1844
75 Correct 14 ms 24284 KB n=2000
76 Correct 17 ms 24276 KB n=2000
77 Correct 16 ms 24292 KB n=2000
78 Correct 16 ms 24276 KB n=2000
79 Correct 17 ms 24268 KB n=2000
80 Correct 16 ms 24292 KB n=2000
81 Correct 15 ms 24276 KB n=2000
82 Correct 16 ms 24240 KB n=2000
83 Correct 15 ms 24276 KB n=2000
84 Correct 21 ms 24320 KB n=2000
85 Correct 15 ms 24276 KB n=2000
86 Correct 16 ms 24340 KB n=2000
87 Correct 15 ms 24276 KB n=2000
88 Correct 17 ms 24404 KB n=2000
89 Correct 14 ms 24372 KB n=2000
90 Correct 15 ms 24404 KB n=2000
91 Correct 14 ms 24292 KB n=2000
92 Correct 702 ms 71216 KB n=200000
93 Correct 806 ms 79328 KB n=200000
94 Correct 546 ms 82784 KB n=200000
95 Correct 692 ms 75104 KB n=200000
96 Correct 651 ms 75252 KB n=200000
97 Correct 806 ms 78368 KB n=200000
98 Correct 718 ms 75084 KB n=200000
99 Correct 813 ms 74988 KB n=200000
100 Correct 687 ms 75288 KB n=200000
101 Correct 508 ms 84004 KB n=200000
102 Correct 412 ms 76240 KB n=200000
103 Correct 422 ms 76256 KB n=200000
104 Correct 418 ms 76328 KB n=200000
105 Correct 421 ms 76232 KB n=200000
106 Correct 410 ms 76288 KB n=200000
107 Correct 461 ms 76304 KB n=200000
108 Correct 749 ms 75096 KB n=200000
109 Correct 735 ms 75112 KB n=200000
110 Correct 780 ms 75196 KB n=200000
111 Correct 693 ms 74644 KB n=200000
112 Correct 523 ms 82900 KB n=200000
113 Correct 807 ms 78668 KB n=200000
114 Correct 763 ms 74604 KB n=200000
115 Correct 1040 ms 76460 KB n=200000
116 Correct 710 ms 75416 KB n=200000
117 Correct 547 ms 83440 KB n=200000
118 Correct 931 ms 77708 KB n=200000
119 Correct 676 ms 75292 KB n=200000
120 Correct 500 ms 83792 KB n=200000
121 Correct 459 ms 83792 KB n=200000
122 Correct 460 ms 84184 KB n=200000
123 Correct 452 ms 76052 KB n=200000
124 Correct 194 ms 38796 KB n=25264