oj.uz

Submission #395419

# Submission time Handle Problem Language Result Execution time Memory
395419 2021-04-28T10:39:51 Z rama_pang Birthday gift (IZhO18_treearray) C++17
100 / 100
 1936 ms 79268 KB 
#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);

  // Solution:
  // If A[] is a sequence, and LCA[] is all possible LCA(x, y) = LCA(A[x], A[x + 1], ..., A[y])
  // Then appending A[] with Z will only add possible LCA = LCA(A[-1], Z).
  // Why?
  // Consider W = LCA(A[-1], Z). Then A[-1] is in some subtree of child of W, Z is in another subtree of W.
  // All other possible LCA involving the new Z must be some ancestor of W. Let this ancestor be L, and
  // the segment be LCA(Y...Z).
  // But then, LCA(Y + 1, Z) != L, so Y and (Y + 1) must be in a different subtree of child of L, so
  // it is already added (LCA(Y, Y+1)).
  //
  // So, we only need to care about 2 adjacent elements in A[]. We can check the LCA() with binary lifting.
  // Time complexity: O(N log N).

  int N, M, Q;
  cin >> N >> M >> Q;

  vector<vector<int>> adj(N);
  for (int i = 1; i < N; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    adj[u].emplace_back(v);
    adj[v].emplace_back(u);
  }

  const int LOG = 18;
  vector<int> depth(N);
  vector<vector<int>> lift(LOG, vector<int>(N, -1));

  const auto Dfs = [&](const auto &self, int u, int p) -> void {
    lift[0][u] = p;
    for (int i = 1; i < LOG; i++) {
      lift[i][u] = lift[i - 1][u] == -1 ? -1 : lift[i - 1][lift[i - 1][u]];
    }
    for (auto v : adj[u]) if (v != p) {
      depth[v] = depth[u] + 1;
      self(self, v, u);
    }
  };
  Dfs(Dfs, 0, -1);

  const auto Lca = [&](int x, int y) {
    if (depth[x] > depth[y]) swap(x, y);

    int diff = depth[y] - depth[x];
    for (int i = 0; i < LOG; i++) {
      if ((diff >> i) & 1) {
        y = lift[i][y];
      }
    }

    assert(depth[x] == depth[y]);

    for (int i = LOG - 1; i >= 0; i--) {
      if (lift[i][x] != lift[i][y]) {
        x = lift[i][x];
        y = lift[i][y];
      }
    }
    return x == y ? x : lift[0][x];
  };

  vector<int> A(M);
  for (int i = 0; i < M; i++) {
    cin >> A[i];
    A[i]--;
  }

  vector<set<pair<int, int>>> ans(N);
  for (int i = 0; i < M; i++) {
    ans[A[i]].emplace(i, i);
  }
  for (int i = 1; i < M; i++) {
    ans[Lca(A[i - 1], A[i])].emplace(i - 1, i);
  }

  while (Q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int i, v;
      cin >> i >> v;
      i--, v--;

      ans[A[i]].erase({i, i});
      if (i - 1 >= 0) ans[Lca(A[i - 1], A[i])].erase({i - 1, i});
      if (i + 1 <  M) ans[Lca(A[i], A[i + 1])].erase({i, i + 1});

      A[i] = v;

      ans[A[i]].insert({i, i});
      if (i - 1 >= 0) ans[Lca(A[i - 1], A[i])].insert({i - 1, i});
      if (i + 1 <  M) ans[Lca(A[i], A[i + 1])].insert({i, i + 1});
    } else if (type == 2) {
      int l, r, v;
      cin >> l >> r >> v;
      l--, r--, v--;
      auto it = ans[v].lower_bound({l, -1});
      if (it != end(ans[v]) && it->second <= r) {
        cout << it->first + 1 << ' ' << it->second + 1 << '\n';
      } else {
        cout << "-1 -1\n";
      }
    }
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 332 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 316 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 336 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 332 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 1 ms 332 KB n=100
24 Correct 1 ms 332 KB n=100
25 Correct 1 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 332 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 332 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 316 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 336 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 332 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 1 ms 332 KB n=100
24 Correct 1 ms 332 KB n=100
25 Correct 1 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 332 KB n=100
28 Correct 2 ms 452 KB n=500
29 Correct 2 ms 460 KB n=500
30 Correct 2 ms 460 KB n=500
31 Correct 2 ms 460 KB n=500
32 Correct 2 ms 460 KB n=500
33 Correct 2 ms 460 KB n=500
34 Correct 2 ms 460 KB n=500
35 Correct 2 ms 456 KB n=500
36 Correct 2 ms 460 KB n=500
37 Correct 2 ms 460 KB n=500
38 Correct 2 ms 452 KB n=500
39 Correct 2 ms 460 KB n=500
40 Correct 2 ms 460 KB n=500
41 Correct 2 ms 460 KB n=500
42 Correct 2 ms 452 KB n=500
43 Correct 2 ms 460 KB n=500
44 Correct 2 ms 460 KB n=500
45 Correct 2 ms 460 KB n=500
46 Correct 2 ms 460 KB n=500
47 Correct 2 ms 460 KB n=500
48 Correct 2 ms 460 KB n=500
49 Correct 2 ms 460 KB n=500
50 Correct 2 ms 452 KB n=500
51 Correct 2 ms 460 KB n=500
52 Correct 2 ms 460 KB n=500
53 Correct 2 ms 460 KB n=500
54 Correct 2 ms 460 KB n=500
55 Correct 1 ms 332 KB n=278
56 Correct 2 ms 460 KB n=500
57 Correct 2 ms 460 KB n=500
58 Correct 2 ms 460 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 332 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 316 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 336 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 332 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 1 ms 332 KB n=100
24 Correct 1 ms 332 KB n=100
25 Correct 1 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 332 KB n=100
28 Correct 2 ms 452 KB n=500
29 Correct 2 ms 460 KB n=500
30 Correct 2 ms 460 KB n=500
31 Correct 2 ms 460 KB n=500
32 Correct 2 ms 460 KB n=500
33 Correct 2 ms 460 KB n=500
34 Correct 2 ms 460 KB n=500
35 Correct 2 ms 456 KB n=500
36 Correct 2 ms 460 KB n=500
37 Correct 2 ms 460 KB n=500
38 Correct 2 ms 452 KB n=500
39 Correct 2 ms 460 KB n=500
40 Correct 2 ms 460 KB n=500
41 Correct 2 ms 460 KB n=500
42 Correct 2 ms 452 KB n=500
43 Correct 2 ms 460 KB n=500
44 Correct 2 ms 460 KB n=500
45 Correct 2 ms 460 KB n=500
46 Correct 2 ms 460 KB n=500
47 Correct 2 ms 460 KB n=500
48 Correct 2 ms 460 KB n=500
49 Correct 2 ms 460 KB n=500
50 Correct 2 ms 452 KB n=500
51 Correct 2 ms 460 KB n=500
52 Correct 2 ms 460 KB n=500
53 Correct 2 ms 460 KB n=500
54 Correct 2 ms 460 KB n=500
55 Correct 1 ms 332 KB n=278
56 Correct 2 ms 460 KB n=500
57 Correct 2 ms 460 KB n=500
58 Correct 2 ms 460 KB n=500
59 Correct 4 ms 844 KB n=2000
60 Correct 5 ms 972 KB n=2000
61 Correct 6 ms 1012 KB n=2000
62 Correct 6 ms 864 KB n=2000
63 Correct 7 ms 844 KB n=2000
64 Correct 5 ms 980 KB n=2000
65 Correct 5 ms 844 KB n=2000
66 Correct 5 ms 972 KB n=2000
67 Correct 6 ms 996 KB n=2000
68 Correct 5 ms 1024 KB n=2000
69 Correct 4 ms 844 KB n=2000
70 Correct 5 ms 924 KB n=2000
71 Correct 4 ms 844 KB n=2000
72 Correct 3 ms 844 KB n=2000
73 Correct 3 ms 844 KB n=2000
74 Correct 6 ms 848 KB n=1844
75 Correct 3 ms 844 KB n=2000
76 Correct 5 ms 844 KB n=2000
77 Correct 5 ms 844 KB n=2000
78 Correct 5 ms 844 KB n=2000
79 Correct 6 ms 908 KB n=2000
80 Correct 5 ms 972 KB n=2000
81 Correct 7 ms 972 KB n=2000
82 Correct 6 ms 880 KB n=2000
83 Correct 5 ms 972 KB n=2000
84 Correct 4 ms 844 KB n=2000
85 Correct 5 ms 972 KB n=2000
86 Correct 5 ms 972 KB n=2000
87 Correct 5 ms 844 KB n=2000
88 Correct 5 ms 972 KB n=2000
89 Correct 6 ms 972 KB n=2000
90 Correct 6 ms 972 KB n=2000
91 Correct 3 ms 844 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB n=5
2 Correct 1 ms 332 KB n=100
3 Correct 1 ms 332 KB n=100
4 Correct 1 ms 332 KB n=100
5 Correct 1 ms 332 KB n=100
6 Correct 1 ms 332 KB n=100
7 Correct 1 ms 316 KB n=100
8 Correct 1 ms 332 KB n=100
9 Correct 1 ms 332 KB n=100
10 Correct 1 ms 336 KB n=100
11 Correct 1 ms 332 KB n=100
12 Correct 1 ms 332 KB n=100
13 Correct 1 ms 332 KB n=100
14 Correct 1 ms 332 KB n=100
15 Correct 1 ms 332 KB n=100
16 Correct 1 ms 332 KB n=100
17 Correct 1 ms 332 KB n=100
18 Correct 1 ms 332 KB n=100
19 Correct 1 ms 332 KB n=100
20 Correct 1 ms 332 KB n=100
21 Correct 1 ms 332 KB n=100
22 Correct 1 ms 332 KB n=100
23 Correct 1 ms 332 KB n=100
24 Correct 1 ms 332 KB n=100
25 Correct 1 ms 332 KB n=100
26 Correct 1 ms 204 KB n=12
27 Correct 1 ms 332 KB n=100
28 Correct 2 ms 452 KB n=500
29 Correct 2 ms 460 KB n=500
30 Correct 2 ms 460 KB n=500
31 Correct 2 ms 460 KB n=500
32 Correct 2 ms 460 KB n=500
33 Correct 2 ms 460 KB n=500
34 Correct 2 ms 460 KB n=500
35 Correct 2 ms 456 KB n=500
36 Correct 2 ms 460 KB n=500
37 Correct 2 ms 460 KB n=500
38 Correct 2 ms 452 KB n=500
39 Correct 2 ms 460 KB n=500
40 Correct 2 ms 460 KB n=500
41 Correct 2 ms 460 KB n=500
42 Correct 2 ms 452 KB n=500
43 Correct 2 ms 460 KB n=500
44 Correct 2 ms 460 KB n=500
45 Correct 2 ms 460 KB n=500
46 Correct 2 ms 460 KB n=500
47 Correct 2 ms 460 KB n=500
48 Correct 2 ms 460 KB n=500
49 Correct 2 ms 460 KB n=500
50 Correct 2 ms 452 KB n=500
51 Correct 2 ms 460 KB n=500
52 Correct 2 ms 460 KB n=500
53 Correct 2 ms 460 KB n=500
54 Correct 2 ms 460 KB n=500
55 Correct 1 ms 332 KB n=278
56 Correct 2 ms 460 KB n=500
57 Correct 2 ms 460 KB n=500
58 Correct 2 ms 460 KB n=500
59 Correct 4 ms 844 KB n=2000
60 Correct 5 ms 972 KB n=2000
61 Correct 6 ms 1012 KB n=2000
62 Correct 6 ms 864 KB n=2000
63 Correct 7 ms 844 KB n=2000
64 Correct 5 ms 980 KB n=2000
65 Correct 5 ms 844 KB n=2000
66 Correct 5 ms 972 KB n=2000
67 Correct 6 ms 996 KB n=2000
68 Correct 5 ms 1024 KB n=2000
69 Correct 4 ms 844 KB n=2000
70 Correct 5 ms 924 KB n=2000
71 Correct 4 ms 844 KB n=2000
72 Correct 3 ms 844 KB n=2000
73 Correct 3 ms 844 KB n=2000
74 Correct 6 ms 848 KB n=1844
75 Correct 3 ms 844 KB n=2000
76 Correct 5 ms 844 KB n=2000
77 Correct 5 ms 844 KB n=2000
78 Correct 5 ms 844 KB n=2000
79 Correct 6 ms 908 KB n=2000
80 Correct 5 ms 972 KB n=2000
81 Correct 7 ms 972 KB n=2000
82 Correct 6 ms 880 KB n=2000
83 Correct 5 ms 972 KB n=2000
84 Correct 4 ms 844 KB n=2000
85 Correct 5 ms 972 KB n=2000
86 Correct 5 ms 972 KB n=2000
87 Correct 5 ms 844 KB n=2000
88 Correct 5 ms 972 KB n=2000
89 Correct 6 ms 972 KB n=2000
90 Correct 6 ms 972 KB n=2000
91 Correct 3 ms 844 KB n=2000
92 Correct 1753 ms 63624 KB n=200000
93 Correct 1866 ms 71612 KB n=200000
94 Correct 1857 ms 77272 KB n=200000
95 Correct 1764 ms 63396 KB n=200000
96 Correct 1785 ms 63428 KB n=200000
97 Correct 1834 ms 70112 KB n=200000
98 Correct 1665 ms 63368 KB n=200000
99 Correct 1825 ms 63628 KB n=200000
100 Correct 1621 ms 63716 KB n=200000
101 Correct 1709 ms 79268 KB n=200000
102 Correct 691 ms 64692 KB n=200000
103 Correct 685 ms 64708 KB n=200000
104 Correct 736 ms 64692 KB n=200000
105 Correct 718 ms 65008 KB n=200000
106 Correct 669 ms 65088 KB n=200000
107 Correct 674 ms 65056 KB n=200000
108 Correct 1524 ms 63560 KB n=200000
109 Correct 1593 ms 63520 KB n=200000
110 Correct 1613 ms 63528 KB n=200000
111 Correct 1382 ms 63028 KB n=200000
112 Correct 1645 ms 77620 KB n=200000
113 Correct 1762 ms 70092 KB n=200000
114 Correct 1404 ms 63108 KB n=200000
115 Correct 1936 ms 66596 KB n=200000
116 Correct 1533 ms 63556 KB n=200000
117 Correct 1718 ms 78420 KB n=200000
118 Correct 1873 ms 68340 KB n=200000
119 Correct 1667 ms 63808 KB n=200000
120 Correct 1743 ms 78536 KB n=200000
121 Correct 1766 ms 78504 KB n=200000
122 Correct 1740 ms 78684 KB n=200000
123 Correct 793 ms 64796 KB n=200000
124 Correct 304 ms 17352 KB n=25264