oj.uz

Submission #319122

# Submission time Handle Problem Language Result Execution time Memory
319122 2020-11-04T01:21:20 Z Fischer Birthday gift (IZhO18_treearray) C++14
100 / 100
 1529 ms 82788 KB 
#include <bits/stdc++.h>
using namespace std;

const int maxn = 2e5 + 10;
vector<int> g[maxn];
using pii = pair<int, int>;
int n, m, q;
int a[maxn];
int st[maxn][18];
int h[maxn];
set<int> cnt[2][maxn];

int T = 0;
void dfs(int x, int p) {
    h[x] = h[p] + 1;
    st[x][0] = p;
    for (int k = 1; k < 18; ++k) {
        st[x][k] = st[st[x][k-1]][k-1];
    }
    for (int v : g[x]) {
        if (v == p) continue;
        dfs(v, x);
    }
}

int lca(int x, int y) {
    if (h[x] > h[y]) swap(x, y);
    for (int k = 17; k >= 0; --k) {
        if (h[st[y][k]] >= h[x]) {
            y = st[y][k];
        }
    }
    if (x == y) return x;
    for (int k = 17; k >= 0; --k) {
        if (st[x][k] != st[y][k]) {
            x = st[x][k];
            y = st[y][k];
        }
    }
    return st[x][0];
}

int main() {
    scanf("%d%d%d", &n, &m, &q);
    for (int i = 0; i < n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    for (int i = 1; i <= m; ++i) {
        scanf("%d", a+i);
    }
    for (int i = 1; i <= m; ++i) {
        cnt[0][a[i]].insert(i);
        if (i < m) {
            cnt[1][lca(a[i], a[i+1])].insert(i);
        }
    }
    while (q--) {
        int type;
        scanf("%d", &type);
        if (type == 1) {
            int pos, v;
            scanf("%d%d", &pos, &v);
            if (pos < m) {
                cnt[1][lca(a[pos], a[pos+1])].erase(pos);
            }
            if (pos > 1) {
                cnt[1][lca(a[pos-1], a[pos])].erase(pos-1);
            }
            cnt[0][a[pos]].erase(pos);
            a[pos] = v;
            cnt[0][a[pos]].insert(pos);
            if (pos < m) {
                cnt[1][lca(a[pos], a[pos+1])].insert(pos);
            }
            if (pos > 1) {
                cnt[1][lca(a[pos-1], a[pos])].insert(pos-1);
            }
        } else {
            int l, r, v;
            scanf("%d%d%d", &l, &r, &v);
            bool ok = 0;
            auto q = cnt[0][v].lower_bound(l);
            if (q != cnt[0][v].end() && *q <= r) {
                printf("%d %d\n", *q, *q);
                continue;
            }
            auto u = cnt[1][v].lower_bound(l);
            if (u != cnt[1][v].end() && *u < r) {
                printf("%d %d\n", *u, *u + 1);
            } else {
                puts("-1 -1");
            }
            
        }
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'int main()':
treearray.cpp:85:18: warning: unused variable 'ok' [-Wunused-variable]
   85 |             bool ok = 0;
      |                  ^~
treearray.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   44 |     scanf("%d%d%d", &n, &m, &q);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |         scanf("%d%d", &u, &v);
      |         ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:53:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   53 |         scanf("%d", a+i);
      |         ~~~~~^~~~~~~~~~~
treearray.cpp:63:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   63 |         scanf("%d", &type);
      |         ~~~~~^~~~~~~~~~~~~
treearray.cpp:66:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   66 |             scanf("%d%d", &pos, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~
treearray.cpp:84:18: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   84 |             scanf("%d%d%d", &l, &r, &v);
      |             ~~~~~^~~~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB n=5
2 Correct 16 ms 23788 KB n=100
3 Correct 16 ms 23788 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 16 ms 23788 KB n=100
6 Correct 17 ms 23788 KB n=100
7 Correct 18 ms 23788 KB n=100
8 Correct 17 ms 23788 KB n=100
9 Correct 16 ms 23788 KB n=100
10 Correct 17 ms 23788 KB n=100
11 Correct 16 ms 23788 KB n=100
12 Correct 16 ms 23788 KB n=100
13 Correct 16 ms 23788 KB n=100
14 Correct 17 ms 23820 KB n=100
15 Correct 16 ms 23788 KB n=100
16 Correct 17 ms 23788 KB n=100
17 Correct 17 ms 23788 KB n=100
18 Correct 16 ms 23788 KB n=100
19 Correct 16 ms 23788 KB n=100
20 Correct 16 ms 23820 KB n=100
21 Correct 17 ms 23788 KB n=100
22 Correct 17 ms 23788 KB n=100
23 Correct 17 ms 23788 KB n=100
24 Correct 16 ms 23788 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 16 ms 23788 KB n=12
27 Correct 16 ms 23788 KB n=100
28 Correct 19 ms 23916 KB n=500
29 Correct 19 ms 23916 KB n=500
30 Correct 18 ms 23916 KB n=500
31 Correct 18 ms 23916 KB n=500
32 Correct 18 ms 23900 KB n=500
33 Correct 17 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 17 ms 23916 KB n=500
36 Correct 19 ms 23916 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 17 ms 23916 KB n=500
40 Correct 17 ms 23916 KB n=500
41 Correct 17 ms 23916 KB n=500
42 Correct 18 ms 23916 KB n=500
43 Correct 19 ms 23916 KB n=500
44 Correct 17 ms 23908 KB n=500
45 Correct 17 ms 23916 KB n=500
46 Correct 17 ms 23916 KB n=500
47 Correct 17 ms 23916 KB n=500
48 Correct 21 ms 24064 KB n=500
49 Correct 17 ms 23916 KB n=500
50 Correct 17 ms 24036 KB n=500
51 Correct 17 ms 23916 KB n=500
52 Correct 17 ms 23916 KB n=500
53 Correct 18 ms 23916 KB n=500
54 Correct 17 ms 23916 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 17 ms 23916 KB n=500
57 Correct 17 ms 24044 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 21 ms 24300 KB n=2000
60 Correct 21 ms 24428 KB n=2000
61 Correct 21 ms 24300 KB n=2000
62 Correct 21 ms 24300 KB n=2000
63 Correct 21 ms 24300 KB n=2000
64 Correct 21 ms 24292 KB n=2000
65 Correct 21 ms 24300 KB n=2000
66 Correct 20 ms 24428 KB n=2000
67 Correct 22 ms 24300 KB n=2000
68 Correct 21 ms 24300 KB n=2000
69 Correct 20 ms 24376 KB n=2000
70 Correct 20 ms 24300 KB n=2000
71 Correct 20 ms 24428 KB n=2000
72 Correct 19 ms 24300 KB n=2000
73 Correct 20 ms 24300 KB n=2000
74 Correct 20 ms 24300 KB n=1844
75 Correct 19 ms 24300 KB n=2000
76 Correct 21 ms 24300 KB n=2000
77 Correct 22 ms 24300 KB n=2000
78 Correct 21 ms 24300 KB n=2000
79 Correct 21 ms 24428 KB n=2000
80 Correct 21 ms 24428 KB n=2000
81 Correct 21 ms 24304 KB n=2000
82 Correct 22 ms 24300 KB n=2000
83 Correct 21 ms 24428 KB n=2000
84 Correct 24 ms 24300 KB n=2000
85 Correct 21 ms 24300 KB n=2000
86 Correct 22 ms 24300 KB n=2000
87 Correct 21 ms 24300 KB n=2000
88 Correct 20 ms 24556 KB n=2000
89 Correct 20 ms 24452 KB n=2000
90 Correct 20 ms 24556 KB n=2000
91 Correct 21 ms 24300 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23788 KB n=5
2 Correct 16 ms 23788 KB n=100
3 Correct 16 ms 23788 KB n=100
4 Correct 17 ms 23916 KB n=100
5 Correct 16 ms 23788 KB n=100
6 Correct 17 ms 23788 KB n=100
7 Correct 18 ms 23788 KB n=100
8 Correct 17 ms 23788 KB n=100
9 Correct 16 ms 23788 KB n=100
10 Correct 17 ms 23788 KB n=100
11 Correct 16 ms 23788 KB n=100
12 Correct 16 ms 23788 KB n=100
13 Correct 16 ms 23788 KB n=100
14 Correct 17 ms 23820 KB n=100
15 Correct 16 ms 23788 KB n=100
16 Correct 17 ms 23788 KB n=100
17 Correct 17 ms 23788 KB n=100
18 Correct 16 ms 23788 KB n=100
19 Correct 16 ms 23788 KB n=100
20 Correct 16 ms 23820 KB n=100
21 Correct 17 ms 23788 KB n=100
22 Correct 17 ms 23788 KB n=100
23 Correct 17 ms 23788 KB n=100
24 Correct 16 ms 23788 KB n=100
25 Correct 16 ms 23916 KB n=100
26 Correct 16 ms 23788 KB n=12
27 Correct 16 ms 23788 KB n=100
28 Correct 19 ms 23916 KB n=500
29 Correct 19 ms 23916 KB n=500
30 Correct 18 ms 23916 KB n=500
31 Correct 18 ms 23916 KB n=500
32 Correct 18 ms 23900 KB n=500
33 Correct 17 ms 23916 KB n=500
34 Correct 18 ms 23916 KB n=500
35 Correct 17 ms 23916 KB n=500
36 Correct 19 ms 23916 KB n=500
37 Correct 17 ms 23916 KB n=500
38 Correct 17 ms 23916 KB n=500
39 Correct 17 ms 23916 KB n=500
40 Correct 17 ms 23916 KB n=500
41 Correct 17 ms 23916 KB n=500
42 Correct 18 ms 23916 KB n=500
43 Correct 19 ms 23916 KB n=500
44 Correct 17 ms 23908 KB n=500
45 Correct 17 ms 23916 KB n=500
46 Correct 17 ms 23916 KB n=500
47 Correct 17 ms 23916 KB n=500
48 Correct 21 ms 24064 KB n=500
49 Correct 17 ms 23916 KB n=500
50 Correct 17 ms 24036 KB n=500
51 Correct 17 ms 23916 KB n=500
52 Correct 17 ms 23916 KB n=500
53 Correct 18 ms 23916 KB n=500
54 Correct 17 ms 23916 KB n=500
55 Correct 17 ms 23916 KB n=278
56 Correct 17 ms 23916 KB n=500
57 Correct 17 ms 24044 KB n=500
58 Correct 17 ms 23916 KB n=500
59 Correct 21 ms 24300 KB n=2000
60 Correct 21 ms 24428 KB n=2000
61 Correct 21 ms 24300 KB n=2000
62 Correct 21 ms 24300 KB n=2000
63 Correct 21 ms 24300 KB n=2000
64 Correct 21 ms 24292 KB n=2000
65 Correct 21 ms 24300 KB n=2000
66 Correct 20 ms 24428 KB n=2000
67 Correct 22 ms 24300 KB n=2000
68 Correct 21 ms 24300 KB n=2000
69 Correct 20 ms 24376 KB n=2000
70 Correct 20 ms 24300 KB n=2000
71 Correct 20 ms 24428 KB n=2000
72 Correct 19 ms 24300 KB n=2000
73 Correct 20 ms 24300 KB n=2000
74 Correct 20 ms 24300 KB n=1844
75 Correct 19 ms 24300 KB n=2000
76 Correct 21 ms 24300 KB n=2000
77 Correct 22 ms 24300 KB n=2000
78 Correct 21 ms 24300 KB n=2000
79 Correct 21 ms 24428 KB n=2000
80 Correct 21 ms 24428 KB n=2000
81 Correct 21 ms 24304 KB n=2000
82 Correct 22 ms 24300 KB n=2000
83 Correct 21 ms 24428 KB n=2000
84 Correct 24 ms 24300 KB n=2000
85 Correct 21 ms 24300 KB n=2000
86 Correct 22 ms 24300 KB n=2000
87 Correct 21 ms 24300 KB n=2000
88 Correct 20 ms 24556 KB n=2000
89 Correct 20 ms 24452 KB n=2000
90 Correct 20 ms 24556 KB n=2000
91 Correct 21 ms 24300 KB n=2000
92 Correct 945 ms 73120 KB n=200000
93 Correct 1345 ms 77924 KB n=200000
94 Correct 1275 ms 81252 KB n=200000
95 Correct 924 ms 72940 KB n=200000
96 Correct 874 ms 72920 KB n=200000
97 Correct 1405 ms 77184 KB n=200000
98 Correct 898 ms 72924 KB n=200000
99 Correct 1176 ms 73404 KB n=200000
100 Correct 912 ms 73048 KB n=200000
101 Correct 1267 ms 82788 KB n=200000
102 Correct 581 ms 74084 KB n=200000
103 Correct 596 ms 74344 KB n=200000
104 Correct 582 ms 74340 KB n=200000
105 Correct 618 ms 74724 KB n=200000
106 Correct 575 ms 74596 KB n=200000
107 Correct 579 ms 74724 KB n=200000
108 Correct 1086 ms 72936 KB n=200000
109 Correct 1060 ms 73060 KB n=200000
110 Correct 1110 ms 73060 KB n=200000
111 Correct 915 ms 72408 KB n=200000
112 Correct 1244 ms 81640 KB n=200000
113 Correct 1373 ms 77028 KB n=200000
114 Correct 945 ms 72536 KB n=200000
115 Correct 1529 ms 75020 KB n=200000
116 Correct 854 ms 73300 KB n=200000
117 Correct 1222 ms 81892 KB n=200000
118 Correct 1430 ms 76052 KB n=200000
119 Correct 849 ms 73100 KB n=200000
120 Correct 1184 ms 81892 KB n=200000
121 Correct 1197 ms 81796 KB n=200000
122 Correct 1196 ms 81764 KB n=200000
123 Correct 589 ms 74472 KB n=200000
124 Correct 297 ms 38628 KB n=25264