oj.uz

Submission #503216

# Submission time Handle Problem Language Result Execution time Memory
503216 2022-01-07T14:23:32 Z Pety Birthday gift (IZhO18_treearray) C++14
100 / 100
 1043 ms 82544 KB 
#include <bits/stdc++.h>

#define ll long long
#define ld long double

using namespace std;

const ll MOD = 1e9 + 7;
const ll INF = 1e9;
const int N = 1e5 + 2;

vector<int>G[200002];
int dp[20][200002], a[200002], lvl[200002], n,m , q;

void dfs (int x, int p) {
  dp[0][x] = p;
  lvl[x] = lvl[p] + 1;
  for (int i = 1; (1 << i) <= n; i++)
    dp[i][x] = dp[i - 1][dp[i - 1][x]];
  for (auto it : G[x])
    if (it != p)
      dfs(it, x);
} 

int lca (int x, int y) {
  if (lvl[x] > lvl[y])
    swap(x, y);
  int d = lvl[y] - lvl[x];
  for (int i = 0; (1 << i) <= n; i++)
    if (d & (1 << i))
      y = dp[i][y];
  if (x == y)
    return x;
  for (int i = 19; i >= 0; i--)
    if (dp[i][x] != dp[i][y]) {
      x = dp[i][x];
      y = dp[i][y];
    }
  return dp[0][x];
}

set<int>node[200002];
set<int>lol[200002];

int main()
{
  ios_base::sync_with_stdio(false);
  cin.tie(0); cout.tie(0);
  cin >> n >> m >> q;
  for (int i = 1; i < n; i++) {
    int x, y;
    cin >> x >> y;
    G[x].push_back(y);
    G[y].push_back(x);
  }
  dfs(1, 0);
  for (int i = 1; i <= m; i++) {
    cin >> a[i];
    lol[a[i]].insert(i);
    if (i > 1) {
      node[lca(a[i - 1], a[i])].insert(i - 1);
    }
  }
  while (q--) {
    int type;
    cin >> type;
    if (type == 1) {
      int poz, x;
      cin >> poz >> x;
      if (poz > 1) {
        node[lca(a[poz - 1], a[poz])].erase(poz - 1);
        node[lca(x, a[poz - 1])].insert(poz - 1);
      }
      if (poz < m) {
        node[lca(a[poz + 1], a[poz])].erase(poz);
        node[lca(x, a[poz + 1])].insert(poz);
      }
      lol[a[poz]].erase(poz);
      lol[x].insert(poz);
      a[poz] = x;
      
    }
    else {
      int l, r, x;
      cin >> l >> r >> x;
      auto it = node[x].lower_bound(l);
      auto it2 = lol[x].lower_bound(l);
      if (it2 != lol[x].end() && (*it2) <= r) {
        cout << (*it2) << " " << (*it2) << "\n";
      }
      else if (it != node[x].end() && (*it) < r) 
        cout << (*it) << " " << (*it) + 1 << "\n";
      else
        cout << "-1 -1\n";
    }
  }
  return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23808 KB n=5
2 Correct 11 ms 23772 KB n=100
3 Correct 11 ms 23784 KB n=100
4 Correct 12 ms 23800 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23804 KB n=100
7 Correct 11 ms 23808 KB n=100
8 Correct 10 ms 23884 KB n=100
9 Correct 15 ms 23880 KB n=100
10 Correct 11 ms 23884 KB n=100
11 Correct 11 ms 23804 KB n=100
12 Correct 11 ms 23884 KB n=100
13 Correct 11 ms 23808 KB n=100
14 Correct 11 ms 23884 KB n=100
15 Correct 10 ms 23884 KB n=100
16 Correct 12 ms 23756 KB n=100
17 Correct 12 ms 23884 KB n=100
18 Correct 11 ms 23872 KB n=100
19 Correct 11 ms 23884 KB n=100
20 Correct 11 ms 23884 KB n=100
21 Correct 11 ms 23816 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 13 ms 23808 KB n=100
24 Correct 11 ms 23808 KB n=100
25 Correct 11 ms 23808 KB n=100
26 Correct 11 ms 23752 KB n=12
27 Correct 11 ms 23808 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23808 KB n=5
2 Correct 11 ms 23772 KB n=100
3 Correct 11 ms 23784 KB n=100
4 Correct 12 ms 23800 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23804 KB n=100
7 Correct 11 ms 23808 KB n=100
8 Correct 10 ms 23884 KB n=100
9 Correct 15 ms 23880 KB n=100
10 Correct 11 ms 23884 KB n=100
11 Correct 11 ms 23804 KB n=100
12 Correct 11 ms 23884 KB n=100
13 Correct 11 ms 23808 KB n=100
14 Correct 11 ms 23884 KB n=100
15 Correct 10 ms 23884 KB n=100
16 Correct 12 ms 23756 KB n=100
17 Correct 12 ms 23884 KB n=100
18 Correct 11 ms 23872 KB n=100
19 Correct 11 ms 23884 KB n=100
20 Correct 11 ms 23884 KB n=100
21 Correct 11 ms 23816 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 13 ms 23808 KB n=100
24 Correct 11 ms 23808 KB n=100
25 Correct 11 ms 23808 KB n=100
26 Correct 11 ms 23752 KB n=12
27 Correct 11 ms 23808 KB n=100
28 Correct 11 ms 23948 KB n=500
29 Correct 12 ms 23884 KB n=500
30 Correct 12 ms 23884 KB n=500
31 Correct 12 ms 23884 KB n=500
32 Correct 13 ms 23944 KB n=500
33 Correct 12 ms 23856 KB n=500
34 Correct 11 ms 23948 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 11 ms 23884 KB n=500
37 Correct 11 ms 23940 KB n=500
38 Correct 12 ms 23940 KB n=500
39 Correct 11 ms 23884 KB n=500
40 Correct 11 ms 23948 KB n=500
41 Correct 12 ms 23952 KB n=500
42 Correct 11 ms 23884 KB n=500
43 Correct 11 ms 23884 KB n=500
44 Correct 11 ms 23884 KB n=500
45 Correct 11 ms 23968 KB n=500
46 Correct 11 ms 23884 KB n=500
47 Correct 11 ms 23936 KB n=500
48 Correct 11 ms 23944 KB n=500
49 Correct 11 ms 23884 KB n=500
50 Correct 11 ms 23980 KB n=500
51 Correct 12 ms 23952 KB n=500
52 Correct 11 ms 23952 KB n=500
53 Correct 12 ms 23884 KB n=500
54 Correct 12 ms 23992 KB n=500
55 Correct 12 ms 23836 KB n=278
56 Correct 13 ms 23908 KB n=500
57 Correct 12 ms 23880 KB n=500
58 Correct 11 ms 23940 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23808 KB n=5
2 Correct 11 ms 23772 KB n=100
3 Correct 11 ms 23784 KB n=100
4 Correct 12 ms 23800 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23804 KB n=100
7 Correct 11 ms 23808 KB n=100
8 Correct 10 ms 23884 KB n=100
9 Correct 15 ms 23880 KB n=100
10 Correct 11 ms 23884 KB n=100
11 Correct 11 ms 23804 KB n=100
12 Correct 11 ms 23884 KB n=100
13 Correct 11 ms 23808 KB n=100
14 Correct 11 ms 23884 KB n=100
15 Correct 10 ms 23884 KB n=100
16 Correct 12 ms 23756 KB n=100
17 Correct 12 ms 23884 KB n=100
18 Correct 11 ms 23872 KB n=100
19 Correct 11 ms 23884 KB n=100
20 Correct 11 ms 23884 KB n=100
21 Correct 11 ms 23816 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 13 ms 23808 KB n=100
24 Correct 11 ms 23808 KB n=100
25 Correct 11 ms 23808 KB n=100
26 Correct 11 ms 23752 KB n=12
27 Correct 11 ms 23808 KB n=100
28 Correct 11 ms 23948 KB n=500
29 Correct 12 ms 23884 KB n=500
30 Correct 12 ms 23884 KB n=500
31 Correct 12 ms 23884 KB n=500
32 Correct 13 ms 23944 KB n=500
33 Correct 12 ms 23856 KB n=500
34 Correct 11 ms 23948 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 11 ms 23884 KB n=500
37 Correct 11 ms 23940 KB n=500
38 Correct 12 ms 23940 KB n=500
39 Correct 11 ms 23884 KB n=500
40 Correct 11 ms 23948 KB n=500
41 Correct 12 ms 23952 KB n=500
42 Correct 11 ms 23884 KB n=500
43 Correct 11 ms 23884 KB n=500
44 Correct 11 ms 23884 KB n=500
45 Correct 11 ms 23968 KB n=500
46 Correct 11 ms 23884 KB n=500
47 Correct 11 ms 23936 KB n=500
48 Correct 11 ms 23944 KB n=500
49 Correct 11 ms 23884 KB n=500
50 Correct 11 ms 23980 KB n=500
51 Correct 12 ms 23952 KB n=500
52 Correct 11 ms 23952 KB n=500
53 Correct 12 ms 23884 KB n=500
54 Correct 12 ms 23992 KB n=500
55 Correct 12 ms 23836 KB n=278
56 Correct 13 ms 23908 KB n=500
57 Correct 12 ms 23880 KB n=500
58 Correct 11 ms 23940 KB n=500
59 Correct 13 ms 24204 KB n=2000
60 Correct 13 ms 24396 KB n=2000
61 Correct 14 ms 24348 KB n=2000
62 Correct 15 ms 24224 KB n=2000
63 Correct 13 ms 24268 KB n=2000
64 Correct 15 ms 24268 KB n=2000
65 Correct 13 ms 24196 KB n=2000
66 Correct 15 ms 24336 KB n=2000
67 Correct 15 ms 24268 KB n=2000
68 Correct 13 ms 24268 KB n=2000
69 Correct 13 ms 24268 KB n=2000
70 Correct 13 ms 24268 KB n=2000
71 Correct 13 ms 24268 KB n=2000
72 Correct 13 ms 24268 KB n=2000
73 Correct 12 ms 24292 KB n=2000
74 Correct 13 ms 24268 KB n=1844
75 Correct 12 ms 24208 KB n=2000
76 Correct 14 ms 24276 KB n=2000
77 Correct 13 ms 24268 KB n=2000
78 Correct 16 ms 24276 KB n=2000
79 Correct 14 ms 24276 KB n=2000
80 Correct 15 ms 24328 KB n=2000
81 Correct 16 ms 24268 KB n=2000
82 Correct 15 ms 24272 KB n=2000
83 Correct 14 ms 24272 KB n=2000
84 Correct 14 ms 24236 KB n=2000
85 Correct 14 ms 24340 KB n=2000
86 Correct 13 ms 24288 KB n=2000
87 Correct 15 ms 24204 KB n=2000
88 Correct 13 ms 24376 KB n=2000
89 Correct 14 ms 24328 KB n=2000
90 Correct 15 ms 24396 KB n=2000
91 Correct 13 ms 24268 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23808 KB n=5
2 Correct 11 ms 23772 KB n=100
3 Correct 11 ms 23784 KB n=100
4 Correct 12 ms 23800 KB n=100
5 Correct 10 ms 23756 KB n=100
6 Correct 11 ms 23804 KB n=100
7 Correct 11 ms 23808 KB n=100
8 Correct 10 ms 23884 KB n=100
9 Correct 15 ms 23880 KB n=100
10 Correct 11 ms 23884 KB n=100
11 Correct 11 ms 23804 KB n=100
12 Correct 11 ms 23884 KB n=100
13 Correct 11 ms 23808 KB n=100
14 Correct 11 ms 23884 KB n=100
15 Correct 10 ms 23884 KB n=100
16 Correct 12 ms 23756 KB n=100
17 Correct 12 ms 23884 KB n=100
18 Correct 11 ms 23872 KB n=100
19 Correct 11 ms 23884 KB n=100
20 Correct 11 ms 23884 KB n=100
21 Correct 11 ms 23816 KB n=100
22 Correct 10 ms 23756 KB n=100
23 Correct 13 ms 23808 KB n=100
24 Correct 11 ms 23808 KB n=100
25 Correct 11 ms 23808 KB n=100
26 Correct 11 ms 23752 KB n=12
27 Correct 11 ms 23808 KB n=100
28 Correct 11 ms 23948 KB n=500
29 Correct 12 ms 23884 KB n=500
30 Correct 12 ms 23884 KB n=500
31 Correct 12 ms 23884 KB n=500
32 Correct 13 ms 23944 KB n=500
33 Correct 12 ms 23856 KB n=500
34 Correct 11 ms 23948 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 11 ms 23884 KB n=500
37 Correct 11 ms 23940 KB n=500
38 Correct 12 ms 23940 KB n=500
39 Correct 11 ms 23884 KB n=500
40 Correct 11 ms 23948 KB n=500
41 Correct 12 ms 23952 KB n=500
42 Correct 11 ms 23884 KB n=500
43 Correct 11 ms 23884 KB n=500
44 Correct 11 ms 23884 KB n=500
45 Correct 11 ms 23968 KB n=500
46 Correct 11 ms 23884 KB n=500
47 Correct 11 ms 23936 KB n=500
48 Correct 11 ms 23944 KB n=500
49 Correct 11 ms 23884 KB n=500
50 Correct 11 ms 23980 KB n=500
51 Correct 12 ms 23952 KB n=500
52 Correct 11 ms 23952 KB n=500
53 Correct 12 ms 23884 KB n=500
54 Correct 12 ms 23992 KB n=500
55 Correct 12 ms 23836 KB n=278
56 Correct 13 ms 23908 KB n=500
57 Correct 12 ms 23880 KB n=500
58 Correct 11 ms 23940 KB n=500
59 Correct 13 ms 24204 KB n=2000
60 Correct 13 ms 24396 KB n=2000
61 Correct 14 ms 24348 KB n=2000
62 Correct 15 ms 24224 KB n=2000
63 Correct 13 ms 24268 KB n=2000
64 Correct 15 ms 24268 KB n=2000
65 Correct 13 ms 24196 KB n=2000
66 Correct 15 ms 24336 KB n=2000
67 Correct 15 ms 24268 KB n=2000
68 Correct 13 ms 24268 KB n=2000
69 Correct 13 ms 24268 KB n=2000
70 Correct 13 ms 24268 KB n=2000
71 Correct 13 ms 24268 KB n=2000
72 Correct 13 ms 24268 KB n=2000
73 Correct 12 ms 24292 KB n=2000
74 Correct 13 ms 24268 KB n=1844
75 Correct 12 ms 24208 KB n=2000
76 Correct 14 ms 24276 KB n=2000
77 Correct 13 ms 24268 KB n=2000
78 Correct 16 ms 24276 KB n=2000
79 Correct 14 ms 24276 KB n=2000
80 Correct 15 ms 24328 KB n=2000
81 Correct 16 ms 24268 KB n=2000
82 Correct 15 ms 24272 KB n=2000
83 Correct 14 ms 24272 KB n=2000
84 Correct 14 ms 24236 KB n=2000
85 Correct 14 ms 24340 KB n=2000
86 Correct 13 ms 24288 KB n=2000
87 Correct 15 ms 24204 KB n=2000
88 Correct 13 ms 24376 KB n=2000
89 Correct 14 ms 24328 KB n=2000
90 Correct 15 ms 24396 KB n=2000
91 Correct 13 ms 24268 KB n=2000
92 Correct 786 ms 72940 KB n=200000
93 Correct 909 ms 77992 KB n=200000
94 Correct 850 ms 81152 KB n=200000
95 Correct 738 ms 72948 KB n=200000
96 Correct 743 ms 72756 KB n=200000
97 Correct 932 ms 76980 KB n=200000
98 Correct 744 ms 72760 KB n=200000
99 Correct 921 ms 72980 KB n=200000
100 Correct 978 ms 72892 KB n=200000
101 Correct 889 ms 82544 KB n=200000
102 Correct 450 ms 73936 KB n=200000
103 Correct 444 ms 73924 KB n=200000
104 Correct 444 ms 73940 KB n=200000
105 Correct 469 ms 74324 KB n=200000
106 Correct 444 ms 74372 KB n=200000
107 Correct 453 ms 74356 KB n=200000
108 Correct 875 ms 72796 KB n=200000
109 Correct 841 ms 72772 KB n=200000
110 Correct 843 ms 72848 KB n=200000
111 Correct 830 ms 72216 KB n=200000
112 Correct 882 ms 81424 KB n=200000
113 Correct 950 ms 76740 KB n=200000
114 Correct 750 ms 72224 KB n=200000
115 Correct 1043 ms 74740 KB n=200000
116 Correct 708 ms 72952 KB n=200000
117 Correct 855 ms 81788 KB n=200000
118 Correct 987 ms 75824 KB n=200000
119 Correct 734 ms 72884 KB n=200000
120 Correct 845 ms 81616 KB n=200000
121 Correct 838 ms 81440 KB n=200000
122 Correct 821 ms 81692 KB n=200000
123 Correct 487 ms 74284 KB n=200000
124 Correct 208 ms 38224 KB n=25264