oj.uz

Submission #863992

# Submission time Handle Problem Language Result Execution time Memory
863992 2023-10-21T16:19:19 Z Dec0Dedd Birthday gift (IZhO18_treearray) C++14
100 / 100
 1219 ms 76880 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 2e5+10;
const int K = 20;

vector<int> G[N];

int up[K][N], a[N], n, m, q, tin[N], tout[N], t;

void dfs(int v, int p) {
    up[0][v]=p; tin[v]=++t;
    for (int i=1; i<K; ++i) up[i][v]=up[i-1][up[i-1][v]];

    for (auto u : G[v]) {
        if (u == p) continue;
        dfs(u, v);
    } tout[v]=t;
}

bool anc(int v, int u) {
    return tin[v] <= tin[u] && tout[u] <= tout[v];
}

int lca(int v, int u) {
    if (anc(v, u)) return v;
    if (anc(u, v)) return u;

    for (int i=K-1; i>=0; --i) {
        if (!anc(up[i][v], u)) v=up[i][v];
    } return up[0][v];
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);
    
    cin>>n>>m>>q;

    for (int i=1; i<n; ++i) {
        int a, b; cin>>a>>b;
        G[a].push_back(b);
        G[b].push_back(a);
    } dfs(1, 1);

    for (int i=1; i<=m; ++i) cin>>a[i];

    set<int> st[n+1], ps[n+1];
    for (int i=1; i+1<=m; ++i) {
        st[lca(a[i], a[i+1])].insert(i);
        ps[a[i]].insert(i);
    } ps[a[n]].insert(n);

    while (q--) {
        int tp; cin>>tp;

        if (tp == 1) {
            int p, v; cin>>p>>v;

            ps[a[p]].erase(p);
            ps[v].insert(p);

            if (m == 1) continue;

            if (p == 1) {
                st[lca(a[p], a[p+1])].erase(p);
                a[p]=v;
                st[lca(a[p], a[p+1])].insert(p);
            } else if (p == m) {
                st[lca(a[p-1], a[p])].erase(p-1);
                a[p]=v;
                st[lca(a[p-1], a[p])].insert(p-1);
            } else {
                st[lca(a[p], a[p+1])].erase(p);
                st[lca(a[p-1], a[p])].erase(p-1);
                a[p]=v;
                st[lca(a[p], a[p+1])].insert(p);
                st[lca(a[p-1], a[p])].insert(p-1);
            }
        } else {
            int l, r, v; cin>>l>>r>>v;

            auto ptr=ps[v].lower_bound(l);
            if (ptr != ps[v].end() && *ptr <= r) {
                cout<<(*ptr)<<" "<<(*ptr)<<"\n";
                continue;
            }

            if (st[v].empty()) cout<<-1<<" "<<-1<<"\n";
            else {
                auto ptr=st[v].lower_bound(l);
                if (ptr == st[v].end()) cout<<-1<<" "<<-1<<"\n";
                else if (*ptr < r) cout<<(*ptr)<<" "<<(*ptr)+1<<"\n";
                else cout<<-1<<" "<<-1<<"\n";
            }
        }
    }
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB n=5
2 Correct 4 ms 22976 KB n=100
3 Correct 4 ms 22876 KB n=100
4 Correct 3 ms 22956 KB n=100
5 Correct 4 ms 22876 KB n=100
6 Correct 4 ms 22876 KB n=100
7 Correct 4 ms 22876 KB n=100
8 Correct 4 ms 22876 KB n=100
9 Correct 4 ms 22876 KB n=100
10 Correct 4 ms 22872 KB n=100
11 Correct 4 ms 22876 KB n=100
12 Correct 4 ms 22876 KB n=100
13 Correct 4 ms 22876 KB n=100
14 Correct 4 ms 22876 KB n=100
15 Correct 3 ms 22876 KB n=100
16 Correct 4 ms 22876 KB n=100
17 Correct 4 ms 22876 KB n=100
18 Correct 5 ms 22876 KB n=100
19 Correct 4 ms 22876 KB n=100
20 Correct 4 ms 22876 KB n=100
21 Correct 4 ms 22872 KB n=100
22 Correct 4 ms 22876 KB n=100
23 Correct 4 ms 22872 KB n=100
24 Correct 4 ms 22872 KB n=100
25 Correct 4 ms 22876 KB n=100
26 Correct 4 ms 22876 KB n=12
27 Correct 3 ms 22888 KB n=100
28 Correct 4 ms 22876 KB n=500
29 Correct 4 ms 22876 KB n=500
30 Correct 4 ms 22876 KB n=500
31 Correct 4 ms 22876 KB n=500
32 Correct 4 ms 22872 KB n=500
33 Correct 4 ms 22872 KB n=500
34 Correct 4 ms 23072 KB n=500
35 Correct 4 ms 22876 KB n=500
36 Correct 4 ms 22876 KB n=500
37 Correct 4 ms 23008 KB n=500
38 Correct 4 ms 23128 KB n=500
39 Correct 4 ms 22968 KB n=500
40 Correct 4 ms 22872 KB n=500
41 Correct 4 ms 23116 KB n=500
42 Correct 4 ms 22872 KB n=500
43 Correct 4 ms 22876 KB n=500
44 Correct 4 ms 22872 KB n=500
45 Correct 4 ms 22876 KB n=500
46 Correct 4 ms 23116 KB n=500
47 Correct 4 ms 22876 KB n=500
48 Correct 4 ms 22960 KB n=500
49 Correct 4 ms 23076 KB n=500
50 Correct 4 ms 22872 KB n=500
51 Correct 4 ms 22872 KB n=500
52 Correct 4 ms 22876 KB n=500
53 Correct 4 ms 22876 KB n=500
54 Correct 4 ms 23020 KB n=500
55 Correct 4 ms 22876 KB n=278
56 Correct 4 ms 22876 KB n=500
57 Correct 4 ms 22876 KB n=500
58 Correct 4 ms 22876 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB n=5
2 Correct 4 ms 22976 KB n=100
3 Correct 4 ms 22876 KB n=100
4 Correct 3 ms 22956 KB n=100
5 Correct 4 ms 22876 KB n=100
6 Correct 4 ms 22876 KB n=100
7 Correct 4 ms 22876 KB n=100
8 Correct 4 ms 22876 KB n=100
9 Correct 4 ms 22876 KB n=100
10 Correct 4 ms 22872 KB n=100
11 Correct 4 ms 22876 KB n=100
12 Correct 4 ms 22876 KB n=100
13 Correct 4 ms 22876 KB n=100
14 Correct 4 ms 22876 KB n=100
15 Correct 3 ms 22876 KB n=100
16 Correct 4 ms 22876 KB n=100
17 Correct 4 ms 22876 KB n=100
18 Correct 5 ms 22876 KB n=100
19 Correct 4 ms 22876 KB n=100
20 Correct 4 ms 22876 KB n=100
21 Correct 4 ms 22872 KB n=100
22 Correct 4 ms 22876 KB n=100
23 Correct 4 ms 22872 KB n=100
24 Correct 4 ms 22872 KB n=100
25 Correct 4 ms 22876 KB n=100
26 Correct 4 ms 22876 KB n=12
27 Correct 3 ms 22888 KB n=100
28 Correct 4 ms 22876 KB n=500
29 Correct 4 ms 22876 KB n=500
30 Correct 4 ms 22876 KB n=500
31 Correct 4 ms 22876 KB n=500
32 Correct 4 ms 22872 KB n=500
33 Correct 4 ms 22872 KB n=500
34 Correct 4 ms 23072 KB n=500
35 Correct 4 ms 22876 KB n=500
36 Correct 4 ms 22876 KB n=500
37 Correct 4 ms 23008 KB n=500
38 Correct 4 ms 23128 KB n=500
39 Correct 4 ms 22968 KB n=500
40 Correct 4 ms 22872 KB n=500
41 Correct 4 ms 23116 KB n=500
42 Correct 4 ms 22872 KB n=500
43 Correct 4 ms 22876 KB n=500
44 Correct 4 ms 22872 KB n=500
45 Correct 4 ms 22876 KB n=500
46 Correct 4 ms 23116 KB n=500
47 Correct 4 ms 22876 KB n=500
48 Correct 4 ms 22960 KB n=500
49 Correct 4 ms 23076 KB n=500
50 Correct 4 ms 22872 KB n=500
51 Correct 4 ms 22872 KB n=500
52 Correct 4 ms 22876 KB n=500
53 Correct 4 ms 22876 KB n=500
54 Correct 4 ms 23020 KB n=500
55 Correct 4 ms 22876 KB n=278
56 Correct 4 ms 22876 KB n=500
57 Correct 4 ms 22876 KB n=500
58 Correct 4 ms 22876 KB n=500
59 Correct 6 ms 23388 KB n=2000
60 Correct 7 ms 23388 KB n=2000
61 Correct 6 ms 23388 KB n=2000
62 Correct 6 ms 23388 KB n=2000
63 Correct 6 ms 23388 KB n=2000
64 Correct 7 ms 23344 KB n=2000
65 Correct 6 ms 23384 KB n=2000
66 Correct 6 ms 23388 KB n=2000
67 Correct 6 ms 23388 KB n=2000
68 Correct 6 ms 23384 KB n=2000
69 Correct 5 ms 23388 KB n=2000
70 Correct 7 ms 23644 KB n=2000
71 Correct 8 ms 23388 KB n=2000
72 Correct 5 ms 23388 KB n=2000
73 Correct 5 ms 23384 KB n=2000
74 Correct 6 ms 23384 KB n=1844
75 Correct 6 ms 23384 KB n=2000
76 Correct 7 ms 23640 KB n=2000
77 Correct 6 ms 23384 KB n=2000
78 Correct 6 ms 23388 KB n=2000
79 Correct 6 ms 23384 KB n=2000
80 Correct 6 ms 23388 KB n=2000
81 Correct 6 ms 23388 KB n=2000
82 Correct 6 ms 23388 KB n=2000
83 Correct 5 ms 23388 KB n=2000
84 Correct 6 ms 23388 KB n=2000
85 Correct 7 ms 23640 KB n=2000
86 Correct 6 ms 23388 KB n=2000
87 Correct 7 ms 23388 KB n=2000
88 Correct 5 ms 23388 KB n=2000
89 Correct 5 ms 23388 KB n=2000
90 Correct 5 ms 23388 KB n=2000
91 Correct 5 ms 23388 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 22876 KB n=5
2 Correct 4 ms 22976 KB n=100
3 Correct 4 ms 22876 KB n=100
4 Correct 3 ms 22956 KB n=100
5 Correct 4 ms 22876 KB n=100
6 Correct 4 ms 22876 KB n=100
7 Correct 4 ms 22876 KB n=100
8 Correct 4 ms 22876 KB n=100
9 Correct 4 ms 22876 KB n=100
10 Correct 4 ms 22872 KB n=100
11 Correct 4 ms 22876 KB n=100
12 Correct 4 ms 22876 KB n=100
13 Correct 4 ms 22876 KB n=100
14 Correct 4 ms 22876 KB n=100
15 Correct 3 ms 22876 KB n=100
16 Correct 4 ms 22876 KB n=100
17 Correct 4 ms 22876 KB n=100
18 Correct 5 ms 22876 KB n=100
19 Correct 4 ms 22876 KB n=100
20 Correct 4 ms 22876 KB n=100
21 Correct 4 ms 22872 KB n=100
22 Correct 4 ms 22876 KB n=100
23 Correct 4 ms 22872 KB n=100
24 Correct 4 ms 22872 KB n=100
25 Correct 4 ms 22876 KB n=100
26 Correct 4 ms 22876 KB n=12
27 Correct 3 ms 22888 KB n=100
28 Correct 4 ms 22876 KB n=500
29 Correct 4 ms 22876 KB n=500
30 Correct 4 ms 22876 KB n=500
31 Correct 4 ms 22876 KB n=500
32 Correct 4 ms 22872 KB n=500
33 Correct 4 ms 22872 KB n=500
34 Correct 4 ms 23072 KB n=500
35 Correct 4 ms 22876 KB n=500
36 Correct 4 ms 22876 KB n=500
37 Correct 4 ms 23008 KB n=500
38 Correct 4 ms 23128 KB n=500
39 Correct 4 ms 22968 KB n=500
40 Correct 4 ms 22872 KB n=500
41 Correct 4 ms 23116 KB n=500
42 Correct 4 ms 22872 KB n=500
43 Correct 4 ms 22876 KB n=500
44 Correct 4 ms 22872 KB n=500
45 Correct 4 ms 22876 KB n=500
46 Correct 4 ms 23116 KB n=500
47 Correct 4 ms 22876 KB n=500
48 Correct 4 ms 22960 KB n=500
49 Correct 4 ms 23076 KB n=500
50 Correct 4 ms 22872 KB n=500
51 Correct 4 ms 22872 KB n=500
52 Correct 4 ms 22876 KB n=500
53 Correct 4 ms 22876 KB n=500
54 Correct 4 ms 23020 KB n=500
55 Correct 4 ms 22876 KB n=278
56 Correct 4 ms 22876 KB n=500
57 Correct 4 ms 22876 KB n=500
58 Correct 4 ms 22876 KB n=500
59 Correct 6 ms 23388 KB n=2000
60 Correct 7 ms 23388 KB n=2000
61 Correct 6 ms 23388 KB n=2000
62 Correct 6 ms 23388 KB n=2000
63 Correct 6 ms 23388 KB n=2000
64 Correct 7 ms 23344 KB n=2000
65 Correct 6 ms 23384 KB n=2000
66 Correct 6 ms 23388 KB n=2000
67 Correct 6 ms 23388 KB n=2000
68 Correct 6 ms 23384 KB n=2000
69 Correct 5 ms 23388 KB n=2000
70 Correct 7 ms 23644 KB n=2000
71 Correct 8 ms 23388 KB n=2000
72 Correct 5 ms 23388 KB n=2000
73 Correct 5 ms 23384 KB n=2000
74 Correct 6 ms 23384 KB n=1844
75 Correct 6 ms 23384 KB n=2000
76 Correct 7 ms 23640 KB n=2000
77 Correct 6 ms 23384 KB n=2000
78 Correct 6 ms 23388 KB n=2000
79 Correct 6 ms 23384 KB n=2000
80 Correct 6 ms 23388 KB n=2000
81 Correct 6 ms 23388 KB n=2000
82 Correct 6 ms 23388 KB n=2000
83 Correct 5 ms 23388 KB n=2000
84 Correct 6 ms 23388 KB n=2000
85 Correct 7 ms 23640 KB n=2000
86 Correct 6 ms 23388 KB n=2000
87 Correct 7 ms 23388 KB n=2000
88 Correct 5 ms 23388 KB n=2000
89 Correct 5 ms 23388 KB n=2000
90 Correct 5 ms 23388 KB n=2000
91 Correct 5 ms 23388 KB n=2000
92 Correct 1120 ms 75336 KB n=200000
93 Correct 790 ms 75856 KB n=200000
94 Correct 464 ms 75600 KB n=200000
95 Correct 1130 ms 75412 KB n=200000
96 Correct 1057 ms 75232 KB n=200000
97 Correct 876 ms 75932 KB n=200000
98 Correct 1174 ms 75312 KB n=200000
99 Correct 1076 ms 75700 KB n=200000
100 Correct 1089 ms 75436 KB n=200000
101 Correct 376 ms 75856 KB n=200000
102 Correct 421 ms 76372 KB n=200000
103 Correct 411 ms 76292 KB n=200000
104 Correct 455 ms 76372 KB n=200000
105 Correct 458 ms 76880 KB n=200000
106 Correct 418 ms 76820 KB n=200000
107 Correct 411 ms 76764 KB n=200000
108 Correct 989 ms 75296 KB n=200000
109 Correct 984 ms 75524 KB n=200000
110 Correct 968 ms 75500 KB n=200000
111 Correct 935 ms 74824 KB n=200000
112 Correct 428 ms 75632 KB n=200000
113 Correct 832 ms 75744 KB n=200000
114 Correct 960 ms 74696 KB n=200000
115 Correct 1219 ms 75716 KB n=200000
116 Correct 1115 ms 75604 KB n=200000
117 Correct 412 ms 75348 KB n=200000
118 Correct 987 ms 75460 KB n=200000
119 Correct 1145 ms 75404 KB n=200000
120 Correct 326 ms 74576 KB n=200000
121 Correct 319 ms 74372 KB n=200000
122 Correct 309 ms 74832 KB n=200000
123 Correct 502 ms 76632 KB n=200000
124 Correct 88 ms 36820 KB n=25264