oj.uz

Submission #339304

# Submission time Handle Problem Language Result Execution time Memory
339304 2020-12-25T03:42:59 Z boykut Birthday gift (IZhO18_treearray) C++14
12 / 100
 4000 ms 10092 KB 
#include <bits/stdc++.h>

using namespace std;

vector <int> g[200001];
vector <int> tree[200001];
int pred[200001], deep[200001], a[200001];

void make_tree(int v, int pre = -1) {
   pred[v] = pre;
   if (pre != -1) deep[v] = deep[pre] + 1;
   else deep[v] = 1;
   for (int to: g[v]) {
      if (to == pred[v]) continue;
      tree[v].push_back(to);
      make_tree(to, v);
   }
}

int lca(int a, int b) {
   while (deep[b] > deep[a]) b = pred[b];
   while (deep[a] > deep[b]) a = pred[a];
   if (a == b)
      return a;
   while (1) {
      a = pred[a];
      b = pred[b];
      if (a == b)
         return a;
   }
   return 1;
}

signed main() {
   ios::sync_with_stdio(0);
   cin.tie(0);
   int n, m, q;
   cin >> n >> m >> q;
   for (int i = 0; i < n - 1; i++) {
      int u, v;
      cin >> u >> v;
      g[u].push_back(v);
      g[v].push_back(u);
   }
   for (int i = 1; i <= m; i++) {
      cin >> a[i];
   }
   make_tree(1);
   for (int i = 0; i < q; i++) {
      int t;
      cin >> t;
      if (t == 1) {
         int pos, v;
         cin >> pos >> v;
         a[pos] = v;
      } else {
         int l, r, v;
         cin >> l >> r >> v;
         int ansx = -1, ansy = -1;
         int LC;
         bool find = false;
         for (int x = l; x <= r && !find; x++) {
            for (int y = x; y <= r && !find; y++) {
               if (y == x) LC = a[y];
               else LC = lca(LC, a[y]);
               if (LC == v) {
                  ansx = x, ansy = y;
                  find = true;
               }
            }
         }
         cout << ansx << ' ' << ansy << '\n';
      }
   }
   return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:21:27: warning: 'LC' may be used uninitialized in this function [-Wmaybe-uninitialized]
   21 |    while (deep[b] > deep[a]) b = pred[b];
      |                     ~~~~~~^
treearray.cpp:60:14: note: 'LC' was declared here
   60 |          int LC;
      |              ^~

Subtask #1
12.0 / 12.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB n=5
2 Correct 7 ms 9728 KB n=100
3 Correct 7 ms 9708 KB n=100
4 Correct 7 ms 9728 KB n=100
5 Correct 7 ms 9708 KB n=100
6 Correct 11 ms 9708 KB n=100
7 Correct 10 ms 9708 KB n=100
8 Correct 8 ms 9720 KB n=100
9 Correct 8 ms 9708 KB n=100
10 Correct 9 ms 9708 KB n=100
11 Correct 9 ms 9708 KB n=100
12 Correct 7 ms 9708 KB n=100
13 Correct 7 ms 9708 KB n=100
14 Correct 7 ms 9708 KB n=100
15 Correct 7 ms 9708 KB n=100
16 Correct 7 ms 9708 KB n=100
17 Correct 14 ms 9708 KB n=100
18 Correct 11 ms 9708 KB n=100
19 Correct 7 ms 9708 KB n=100
20 Correct 11 ms 9708 KB n=100
21 Correct 10 ms 9708 KB n=100
22 Correct 7 ms 9708 KB n=100
23 Correct 17 ms 9708 KB n=100
24 Correct 19 ms 9708 KB n=100
25 Correct 10 ms 9708 KB n=100
26 Correct 7 ms 9708 KB n=12
27 Correct 9 ms 9708 KB n=100
28 Correct 7 ms 9836 KB n=500
29 Correct 2454 ms 9888 KB n=500
30 Correct 1085 ms 9964 KB n=500
31 Correct 1568 ms 9964 KB n=500
32 Correct 8 ms 9836 KB n=500
33 Correct 757 ms 9964 KB n=500
34 Correct 7 ms 9836 KB n=500
35 Correct 2106 ms 9888 KB n=500
36 Correct 835 ms 10092 KB n=500
37 Correct 937 ms 10092 KB n=500
38 Correct 981 ms 10092 KB n=500
39 Correct 84 ms 9836 KB n=500
40 Correct 90 ms 9836 KB n=500
41 Correct 89 ms 9836 KB n=500
42 Correct 402 ms 9836 KB n=500
43 Correct 474 ms 9964 KB n=500
44 Correct 467 ms 9836 KB n=500
45 Correct 8 ms 9836 KB n=500
46 Correct 2177 ms 9888 KB n=500
47 Correct 1712 ms 9964 KB n=500
48 Correct 7 ms 9836 KB n=500
49 Correct 1667 ms 9964 KB n=500
50 Correct 21 ms 9836 KB n=500
51 Correct 1995 ms 9964 KB n=500
52 Correct 3864 ms 9888 KB n=500
53 Correct 1569 ms 9964 KB n=500
54 Correct 1536 ms 9964 KB n=500
55 Correct 148 ms 9964 KB n=278
56 Execution timed out 4048 ms 9836 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB n=5
2 Correct 7 ms 9728 KB n=100
3 Correct 7 ms 9708 KB n=100
4 Correct 7 ms 9728 KB n=100
5 Correct 7 ms 9708 KB n=100
6 Correct 11 ms 9708 KB n=100
7 Correct 10 ms 9708 KB n=100
8 Correct 8 ms 9720 KB n=100
9 Correct 8 ms 9708 KB n=100
10 Correct 9 ms 9708 KB n=100
11 Correct 9 ms 9708 KB n=100
12 Correct 7 ms 9708 KB n=100
13 Correct 7 ms 9708 KB n=100
14 Correct 7 ms 9708 KB n=100
15 Correct 7 ms 9708 KB n=100
16 Correct 7 ms 9708 KB n=100
17 Correct 14 ms 9708 KB n=100
18 Correct 11 ms 9708 KB n=100
19 Correct 7 ms 9708 KB n=100
20 Correct 11 ms 9708 KB n=100
21 Correct 10 ms 9708 KB n=100
22 Correct 7 ms 9708 KB n=100
23 Correct 17 ms 9708 KB n=100
24 Correct 19 ms 9708 KB n=100
25 Correct 10 ms 9708 KB n=100
26 Correct 7 ms 9708 KB n=12
27 Correct 9 ms 9708 KB n=100
28 Correct 7 ms 9836 KB n=500
29 Correct 2454 ms 9888 KB n=500
30 Correct 1085 ms 9964 KB n=500
31 Correct 1568 ms 9964 KB n=500
32 Correct 8 ms 9836 KB n=500
33 Correct 757 ms 9964 KB n=500
34 Correct 7 ms 9836 KB n=500
35 Correct 2106 ms 9888 KB n=500
36 Correct 835 ms 10092 KB n=500
37 Correct 937 ms 10092 KB n=500
38 Correct 981 ms 10092 KB n=500
39 Correct 84 ms 9836 KB n=500
40 Correct 90 ms 9836 KB n=500
41 Correct 89 ms 9836 KB n=500
42 Correct 402 ms 9836 KB n=500
43 Correct 474 ms 9964 KB n=500
44 Correct 467 ms 9836 KB n=500
45 Correct 8 ms 9836 KB n=500
46 Correct 2177 ms 9888 KB n=500
47 Correct 1712 ms 9964 KB n=500
48 Correct 7 ms 9836 KB n=500
49 Correct 1667 ms 9964 KB n=500
50 Correct 21 ms 9836 KB n=500
51 Correct 1995 ms 9964 KB n=500
52 Correct 3864 ms 9888 KB n=500
53 Correct 1569 ms 9964 KB n=500
54 Correct 1536 ms 9964 KB n=500
55 Correct 148 ms 9964 KB n=278
56 Execution timed out 4048 ms 9836 KB Time limit exceeded
57 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 9708 KB n=5
2 Correct 7 ms 9728 KB n=100
3 Correct 7 ms 9708 KB n=100
4 Correct 7 ms 9728 KB n=100
5 Correct 7 ms 9708 KB n=100
6 Correct 11 ms 9708 KB n=100
7 Correct 10 ms 9708 KB n=100
8 Correct 8 ms 9720 KB n=100
9 Correct 8 ms 9708 KB n=100
10 Correct 9 ms 9708 KB n=100
11 Correct 9 ms 9708 KB n=100
12 Correct 7 ms 9708 KB n=100
13 Correct 7 ms 9708 KB n=100
14 Correct 7 ms 9708 KB n=100
15 Correct 7 ms 9708 KB n=100
16 Correct 7 ms 9708 KB n=100
17 Correct 14 ms 9708 KB n=100
18 Correct 11 ms 9708 KB n=100
19 Correct 7 ms 9708 KB n=100
20 Correct 11 ms 9708 KB n=100
21 Correct 10 ms 9708 KB n=100
22 Correct 7 ms 9708 KB n=100
23 Correct 17 ms 9708 KB n=100
24 Correct 19 ms 9708 KB n=100
25 Correct 10 ms 9708 KB n=100
26 Correct 7 ms 9708 KB n=12
27 Correct 9 ms 9708 KB n=100
28 Correct 7 ms 9836 KB n=500
29 Correct 2454 ms 9888 KB n=500
30 Correct 1085 ms 9964 KB n=500
31 Correct 1568 ms 9964 KB n=500
32 Correct 8 ms 9836 KB n=500
33 Correct 757 ms 9964 KB n=500
34 Correct 7 ms 9836 KB n=500
35 Correct 2106 ms 9888 KB n=500
36 Correct 835 ms 10092 KB n=500
37 Correct 937 ms 10092 KB n=500
38 Correct 981 ms 10092 KB n=500
39 Correct 84 ms 9836 KB n=500
40 Correct 90 ms 9836 KB n=500
41 Correct 89 ms 9836 KB n=500
42 Correct 402 ms 9836 KB n=500
43 Correct 474 ms 9964 KB n=500
44 Correct 467 ms 9836 KB n=500
45 Correct 8 ms 9836 KB n=500
46 Correct 2177 ms 9888 KB n=500
47 Correct 1712 ms 9964 KB n=500
48 Correct 7 ms 9836 KB n=500
49 Correct 1667 ms 9964 KB n=500
50 Correct 21 ms 9836 KB n=500
51 Correct 1995 ms 9964 KB n=500
52 Correct 3864 ms 9888 KB n=500
53 Correct 1569 ms 9964 KB n=500
54 Correct 1536 ms 9964 KB n=500
55 Correct 148 ms 9964 KB n=278
56 Execution timed out 4048 ms 9836 KB Time limit exceeded
57 Halted 0 ms 0 KB -