oj.uz

Submission #651308

# Submission time Handle Problem Language Result Execution time Memory
651308 2022-10-18T08:19:04 Z Astrayt Birthday gift (IZhO18_treearray) C++17
100 / 100
 2686 ms 92472 KB 
//君の手を握ってしまったら
//孤独を知らないこの街には
//もう二度と帰ってくることはできないのでしょう
//君が手を差し伸べた 光で影が生まれる
//歌って聞かせて この話の続き
//連れて行って見たことない星まで
//さユリ - 花の塔
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define starburst ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pii pair<int,int>
#define pb push_back
#define ff first
#define ss second
#define maxn 200005

int a[maxn], dep[maxn], anc[21][maxn];
vector<int> adj[maxn];
set<int> pos[maxn], pos2[maxn];

void dfs(int u, int p, int d){
    dep[u] = d;
    for(int v:adj[u]){
        if(v == p) continue;
        anc[0][v] = u;
        dfs(v, u, d + 1);
    }
}

int lca(int u, int v){
    if(dep[v] > dep[u]) swap(u, v);
    for(int i = 20; i >= 0; --i){
        if(dep[anc[i][u]] >= dep[v]) u = anc[i][u];
    }
    if(u == v) return u;
    for(int i = 20; i >= 0; --i){
        if(anc[i][u] != anc[i][v]) u = anc[i][u], v = anc[i][v];
    }
    return anc[0][u];
}

void solve(){
    int n, m, q; cin >> n >> m >> q;
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v;
        adj[u].pb(v); adj[v].pb(u);
    }
    for(int i = 0; i <= 20; ++i) anc[i][1] = 1;
    dfs(1, 0, 0);
    for(int i = 1; i <= 20; ++i){
        for(int v = 2; v <= n; ++v){
            anc[i][v] = anc[i - 1][anc[i - 1][v]];
        }
    }
    for(int i = 1; i <= m; ++i) cin >> a[i], pos2[a[i]].insert(i);
    for(int i = 1; i < m; ++i){
        pos[lca(a[i], a[i + 1])].insert(i);
    }
    for(int i = 1; i <= q; ++i){
        int t, l, r; cin >> t >> l >> r;
        if(t == 1){
            pos2[a[l]].erase(l);
            pos2[r].insert(l);
            if(l != n){
                int u = lca(a[l], a[l + 1]);
                pos[u].erase(l);
                u = lca(r, a[l + 1]);
                pos[u].insert(l);
            }
            if(l != 1){
                int u = lca(a[l], a[l - 1]);
                pos[u].erase(l - 1);
                u = lca(r, a[l - 1]);
                pos[u].insert(l - 1);
            }
            a[l] = r;
        }else{
            int v; cin >> v;
            auto x = pos2[v].lower_bound(l);
            if(x != pos2[v].end() && *x <= r) {
                cout << *x << ' ' << *x << '\n';
                continue;
            }
            x = pos[v].lower_bound(l);
            if(x != pos[v].end() && *x < r){
                cout << *x << ' ' << (*x) + 1 << '\n';
            }else cout << "-1 -1\n";
        }
    }
}

signed main(){
    starburst
    int t = 1; //cin >> t;
    while(t--) solve();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23920 KB n=5
2 Correct 13 ms 23888 KB n=100
3 Correct 12 ms 23924 KB n=100
4 Correct 13 ms 24020 KB n=100
5 Correct 13 ms 23880 KB n=100
6 Correct 12 ms 23892 KB n=100
7 Correct 12 ms 23892 KB n=100
8 Correct 13 ms 23892 KB n=100
9 Correct 12 ms 23888 KB n=100
10 Correct 15 ms 23892 KB n=100
11 Correct 12 ms 23948 KB n=100
12 Correct 12 ms 23892 KB n=100
13 Correct 13 ms 23972 KB n=100
14 Correct 12 ms 23960 KB n=100
15 Correct 12 ms 23892 KB n=100
16 Correct 13 ms 23992 KB n=100
17 Correct 14 ms 23892 KB n=100
18 Correct 12 ms 23892 KB n=100
19 Correct 14 ms 23988 KB n=100
20 Correct 15 ms 23892 KB n=100
21 Correct 13 ms 23892 KB n=100
22 Correct 13 ms 23996 KB n=100
23 Correct 12 ms 23936 KB n=100
24 Correct 12 ms 23880 KB n=100
25 Correct 12 ms 23892 KB n=100
26 Correct 13 ms 23920 KB n=12
27 Correct 13 ms 23892 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23920 KB n=5
2 Correct 13 ms 23888 KB n=100
3 Correct 12 ms 23924 KB n=100
4 Correct 13 ms 24020 KB n=100
5 Correct 13 ms 23880 KB n=100
6 Correct 12 ms 23892 KB n=100
7 Correct 12 ms 23892 KB n=100
8 Correct 13 ms 23892 KB n=100
9 Correct 12 ms 23888 KB n=100
10 Correct 15 ms 23892 KB n=100
11 Correct 12 ms 23948 KB n=100
12 Correct 12 ms 23892 KB n=100
13 Correct 13 ms 23972 KB n=100
14 Correct 12 ms 23960 KB n=100
15 Correct 12 ms 23892 KB n=100
16 Correct 13 ms 23992 KB n=100
17 Correct 14 ms 23892 KB n=100
18 Correct 12 ms 23892 KB n=100
19 Correct 14 ms 23988 KB n=100
20 Correct 15 ms 23892 KB n=100
21 Correct 13 ms 23892 KB n=100
22 Correct 13 ms 23996 KB n=100
23 Correct 12 ms 23936 KB n=100
24 Correct 12 ms 23880 KB n=100
25 Correct 12 ms 23892 KB n=100
26 Correct 13 ms 23920 KB n=12
27 Correct 13 ms 23892 KB n=100
28 Correct 14 ms 24128 KB n=500
29 Correct 13 ms 24020 KB n=500
30 Correct 14 ms 24020 KB n=500
31 Correct 13 ms 24020 KB n=500
32 Correct 13 ms 24100 KB n=500
33 Correct 13 ms 24012 KB n=500
34 Correct 13 ms 24020 KB n=500
35 Correct 13 ms 24032 KB n=500
36 Correct 13 ms 24020 KB n=500
37 Correct 13 ms 24040 KB n=500
38 Correct 13 ms 24032 KB n=500
39 Correct 13 ms 24020 KB n=500
40 Correct 13 ms 24140 KB n=500
41 Correct 13 ms 24020 KB n=500
42 Correct 13 ms 24020 KB n=500
43 Correct 12 ms 24132 KB n=500
44 Correct 13 ms 24132 KB n=500
45 Correct 13 ms 24076 KB n=500
46 Correct 13 ms 24044 KB n=500
47 Correct 13 ms 24080 KB n=500
48 Correct 13 ms 24076 KB n=500
49 Correct 16 ms 24148 KB n=500
50 Correct 14 ms 24020 KB n=500
51 Correct 13 ms 24020 KB n=500
52 Correct 14 ms 24112 KB n=500
53 Correct 13 ms 24076 KB n=500
54 Correct 13 ms 24020 KB n=500
55 Correct 14 ms 24072 KB n=278
56 Correct 13 ms 24020 KB n=500
57 Correct 13 ms 24072 KB n=500
58 Correct 13 ms 24020 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23920 KB n=5
2 Correct 13 ms 23888 KB n=100
3 Correct 12 ms 23924 KB n=100
4 Correct 13 ms 24020 KB n=100
5 Correct 13 ms 23880 KB n=100
6 Correct 12 ms 23892 KB n=100
7 Correct 12 ms 23892 KB n=100
8 Correct 13 ms 23892 KB n=100
9 Correct 12 ms 23888 KB n=100
10 Correct 15 ms 23892 KB n=100
11 Correct 12 ms 23948 KB n=100
12 Correct 12 ms 23892 KB n=100
13 Correct 13 ms 23972 KB n=100
14 Correct 12 ms 23960 KB n=100
15 Correct 12 ms 23892 KB n=100
16 Correct 13 ms 23992 KB n=100
17 Correct 14 ms 23892 KB n=100
18 Correct 12 ms 23892 KB n=100
19 Correct 14 ms 23988 KB n=100
20 Correct 15 ms 23892 KB n=100
21 Correct 13 ms 23892 KB n=100
22 Correct 13 ms 23996 KB n=100
23 Correct 12 ms 23936 KB n=100
24 Correct 12 ms 23880 KB n=100
25 Correct 12 ms 23892 KB n=100
26 Correct 13 ms 23920 KB n=12
27 Correct 13 ms 23892 KB n=100
28 Correct 14 ms 24128 KB n=500
29 Correct 13 ms 24020 KB n=500
30 Correct 14 ms 24020 KB n=500
31 Correct 13 ms 24020 KB n=500
32 Correct 13 ms 24100 KB n=500
33 Correct 13 ms 24012 KB n=500
34 Correct 13 ms 24020 KB n=500
35 Correct 13 ms 24032 KB n=500
36 Correct 13 ms 24020 KB n=500
37 Correct 13 ms 24040 KB n=500
38 Correct 13 ms 24032 KB n=500
39 Correct 13 ms 24020 KB n=500
40 Correct 13 ms 24140 KB n=500
41 Correct 13 ms 24020 KB n=500
42 Correct 13 ms 24020 KB n=500
43 Correct 12 ms 24132 KB n=500
44 Correct 13 ms 24132 KB n=500
45 Correct 13 ms 24076 KB n=500
46 Correct 13 ms 24044 KB n=500
47 Correct 13 ms 24080 KB n=500
48 Correct 13 ms 24076 KB n=500
49 Correct 16 ms 24148 KB n=500
50 Correct 14 ms 24020 KB n=500
51 Correct 13 ms 24020 KB n=500
52 Correct 14 ms 24112 KB n=500
53 Correct 13 ms 24076 KB n=500
54 Correct 13 ms 24020 KB n=500
55 Correct 14 ms 24072 KB n=278
56 Correct 13 ms 24020 KB n=500
57 Correct 13 ms 24072 KB n=500
58 Correct 13 ms 24020 KB n=500
59 Correct 17 ms 24592 KB n=2000
60 Correct 18 ms 24612 KB n=2000
61 Correct 16 ms 24588 KB n=2000
62 Correct 17 ms 24592 KB n=2000
63 Correct 17 ms 24588 KB n=2000
64 Correct 17 ms 24552 KB n=2000
65 Correct 17 ms 24660 KB n=2000
66 Correct 17 ms 24676 KB n=2000
67 Correct 18 ms 24596 KB n=2000
68 Correct 16 ms 24660 KB n=2000
69 Correct 15 ms 24584 KB n=2000
70 Correct 15 ms 24660 KB n=2000
71 Correct 16 ms 24640 KB n=2000
72 Correct 15 ms 24604 KB n=2000
73 Correct 15 ms 24532 KB n=2000
74 Correct 17 ms 24584 KB n=1844
75 Correct 15 ms 24572 KB n=2000
76 Correct 17 ms 24532 KB n=2000
77 Correct 19 ms 24532 KB n=2000
78 Correct 18 ms 24532 KB n=2000
79 Correct 18 ms 24652 KB n=2000
80 Correct 16 ms 24660 KB n=2000
81 Correct 16 ms 24548 KB n=2000
82 Correct 16 ms 24532 KB n=2000
83 Correct 16 ms 24640 KB n=2000
84 Correct 18 ms 24532 KB n=2000
85 Correct 16 ms 24568 KB n=2000
86 Correct 17 ms 24584 KB n=2000
87 Correct 18 ms 24556 KB n=2000
88 Correct 15 ms 24572 KB n=2000
89 Correct 16 ms 24532 KB n=2000
90 Correct 16 ms 24612 KB n=2000
91 Correct 15 ms 24532 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23920 KB n=5
2 Correct 13 ms 23888 KB n=100
3 Correct 12 ms 23924 KB n=100
4 Correct 13 ms 24020 KB n=100
5 Correct 13 ms 23880 KB n=100
6 Correct 12 ms 23892 KB n=100
7 Correct 12 ms 23892 KB n=100
8 Correct 13 ms 23892 KB n=100
9 Correct 12 ms 23888 KB n=100
10 Correct 15 ms 23892 KB n=100
11 Correct 12 ms 23948 KB n=100
12 Correct 12 ms 23892 KB n=100
13 Correct 13 ms 23972 KB n=100
14 Correct 12 ms 23960 KB n=100
15 Correct 12 ms 23892 KB n=100
16 Correct 13 ms 23992 KB n=100
17 Correct 14 ms 23892 KB n=100
18 Correct 12 ms 23892 KB n=100
19 Correct 14 ms 23988 KB n=100
20 Correct 15 ms 23892 KB n=100
21 Correct 13 ms 23892 KB n=100
22 Correct 13 ms 23996 KB n=100
23 Correct 12 ms 23936 KB n=100
24 Correct 12 ms 23880 KB n=100
25 Correct 12 ms 23892 KB n=100
26 Correct 13 ms 23920 KB n=12
27 Correct 13 ms 23892 KB n=100
28 Correct 14 ms 24128 KB n=500
29 Correct 13 ms 24020 KB n=500
30 Correct 14 ms 24020 KB n=500
31 Correct 13 ms 24020 KB n=500
32 Correct 13 ms 24100 KB n=500
33 Correct 13 ms 24012 KB n=500
34 Correct 13 ms 24020 KB n=500
35 Correct 13 ms 24032 KB n=500
36 Correct 13 ms 24020 KB n=500
37 Correct 13 ms 24040 KB n=500
38 Correct 13 ms 24032 KB n=500
39 Correct 13 ms 24020 KB n=500
40 Correct 13 ms 24140 KB n=500
41 Correct 13 ms 24020 KB n=500
42 Correct 13 ms 24020 KB n=500
43 Correct 12 ms 24132 KB n=500
44 Correct 13 ms 24132 KB n=500
45 Correct 13 ms 24076 KB n=500
46 Correct 13 ms 24044 KB n=500
47 Correct 13 ms 24080 KB n=500
48 Correct 13 ms 24076 KB n=500
49 Correct 16 ms 24148 KB n=500
50 Correct 14 ms 24020 KB n=500
51 Correct 13 ms 24020 KB n=500
52 Correct 14 ms 24112 KB n=500
53 Correct 13 ms 24076 KB n=500
54 Correct 13 ms 24020 KB n=500
55 Correct 14 ms 24072 KB n=278
56 Correct 13 ms 24020 KB n=500
57 Correct 13 ms 24072 KB n=500
58 Correct 13 ms 24020 KB n=500
59 Correct 17 ms 24592 KB n=2000
60 Correct 18 ms 24612 KB n=2000
61 Correct 16 ms 24588 KB n=2000
62 Correct 17 ms 24592 KB n=2000
63 Correct 17 ms 24588 KB n=2000
64 Correct 17 ms 24552 KB n=2000
65 Correct 17 ms 24660 KB n=2000
66 Correct 17 ms 24676 KB n=2000
67 Correct 18 ms 24596 KB n=2000
68 Correct 16 ms 24660 KB n=2000
69 Correct 15 ms 24584 KB n=2000
70 Correct 15 ms 24660 KB n=2000
71 Correct 16 ms 24640 KB n=2000
72 Correct 15 ms 24604 KB n=2000
73 Correct 15 ms 24532 KB n=2000
74 Correct 17 ms 24584 KB n=1844
75 Correct 15 ms 24572 KB n=2000
76 Correct 17 ms 24532 KB n=2000
77 Correct 19 ms 24532 KB n=2000
78 Correct 18 ms 24532 KB n=2000
79 Correct 18 ms 24652 KB n=2000
80 Correct 16 ms 24660 KB n=2000
81 Correct 16 ms 24548 KB n=2000
82 Correct 16 ms 24532 KB n=2000
83 Correct 16 ms 24640 KB n=2000
84 Correct 18 ms 24532 KB n=2000
85 Correct 16 ms 24568 KB n=2000
86 Correct 17 ms 24584 KB n=2000
87 Correct 18 ms 24556 KB n=2000
88 Correct 15 ms 24572 KB n=2000
89 Correct 16 ms 24532 KB n=2000
90 Correct 16 ms 24612 KB n=2000
91 Correct 15 ms 24532 KB n=2000
92 Correct 1974 ms 87744 KB n=200000
93 Correct 2173 ms 90052 KB n=200000
94 Correct 1953 ms 92060 KB n=200000
95 Correct 1910 ms 87552 KB n=200000
96 Correct 1935 ms 87664 KB n=200000
97 Correct 2219 ms 89392 KB n=200000
98 Correct 1971 ms 87536 KB n=200000
99 Correct 2507 ms 87132 KB n=200000
100 Correct 1939 ms 87576 KB n=200000
101 Correct 1795 ms 92408 KB n=200000
102 Correct 903 ms 88704 KB n=200000
103 Correct 880 ms 88624 KB n=200000
104 Correct 898 ms 88640 KB n=200000
105 Correct 924 ms 88496 KB n=200000
106 Correct 885 ms 88316 KB n=200000
107 Correct 944 ms 88668 KB n=200000
108 Correct 2387 ms 87368 KB n=200000
109 Correct 2288 ms 87372 KB n=200000
110 Correct 2440 ms 87324 KB n=200000
111 Correct 1689 ms 87652 KB n=200000
112 Correct 1853 ms 92004 KB n=200000
113 Correct 2196 ms 89468 KB n=200000
114 Correct 1655 ms 87452 KB n=200000
115 Correct 2686 ms 87972 KB n=200000
116 Correct 1898 ms 87540 KB n=200000
117 Correct 1846 ms 92004 KB n=200000
118 Correct 2358 ms 88636 KB n=200000
119 Correct 1882 ms 87208 KB n=200000
120 Correct 1716 ms 92124 KB n=200000
121 Correct 1704 ms 91956 KB n=200000
122 Correct 1710 ms 92472 KB n=200000
123 Correct 898 ms 88100 KB n=200000
124 Correct 345 ms 39296 KB n=25264