oj.uz

Submission #651303

# Submission time Handle Problem Language Result Execution time Memory
651303 2022-10-18T07:53:54 Z Astrayt Birthday gift (IZhO18_treearray) C++17
12 / 100
 18 ms 24132 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);
    }
    anc[0][1] = 1;
    dfs(1, 0, 0);
    for(int i = 1; i <= 20; ++i){
        for(int v = 1; 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(i != 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 23892 KB n=5
2 Correct 15 ms 23960 KB n=100
3 Correct 13 ms 24000 KB n=100
4 Correct 12 ms 23988 KB n=100
5 Correct 13 ms 23892 KB n=100
6 Correct 13 ms 23940 KB n=100
7 Correct 12 ms 23940 KB n=100
8 Correct 14 ms 23948 KB n=100
9 Correct 14 ms 23932 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 12 ms 23944 KB n=100
12 Correct 13 ms 23892 KB n=100
13 Correct 13 ms 24020 KB n=100
14 Correct 13 ms 23936 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23892 KB n=100
17 Correct 13 ms 23940 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 16 ms 23944 KB n=100
20 Correct 13 ms 23936 KB n=100
21 Correct 14 ms 23972 KB n=100
22 Correct 13 ms 23892 KB n=100
23 Correct 14 ms 23932 KB n=100
24 Correct 13 ms 23940 KB n=100
25 Correct 13 ms 23868 KB n=100
26 Correct 13 ms 23936 KB n=12
27 Correct 13 ms 24000 KB n=100

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 15 ms 23960 KB n=100
3 Correct 13 ms 24000 KB n=100
4 Correct 12 ms 23988 KB n=100
5 Correct 13 ms 23892 KB n=100
6 Correct 13 ms 23940 KB n=100
7 Correct 12 ms 23940 KB n=100
8 Correct 14 ms 23948 KB n=100
9 Correct 14 ms 23932 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 12 ms 23944 KB n=100
12 Correct 13 ms 23892 KB n=100
13 Correct 13 ms 24020 KB n=100
14 Correct 13 ms 23936 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23892 KB n=100
17 Correct 13 ms 23940 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 16 ms 23944 KB n=100
20 Correct 13 ms 23936 KB n=100
21 Correct 14 ms 23972 KB n=100
22 Correct 13 ms 23892 KB n=100
23 Correct 14 ms 23932 KB n=100
24 Correct 13 ms 23940 KB n=100
25 Correct 13 ms 23868 KB n=100
26 Correct 13 ms 23936 KB n=12
27 Correct 13 ms 24000 KB n=100
28 Correct 13 ms 24020 KB n=500
29 Correct 14 ms 24132 KB n=500
30 Correct 15 ms 24076 KB n=500
31 Correct 18 ms 24128 KB n=500
32 Correct 17 ms 24020 KB n=500
33 Correct 14 ms 24092 KB n=500
34 Correct 13 ms 24020 KB n=500
35 Incorrect 16 ms 24072 KB Wrong range.
36 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 15 ms 23960 KB n=100
3 Correct 13 ms 24000 KB n=100
4 Correct 12 ms 23988 KB n=100
5 Correct 13 ms 23892 KB n=100
6 Correct 13 ms 23940 KB n=100
7 Correct 12 ms 23940 KB n=100
8 Correct 14 ms 23948 KB n=100
9 Correct 14 ms 23932 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 12 ms 23944 KB n=100
12 Correct 13 ms 23892 KB n=100
13 Correct 13 ms 24020 KB n=100
14 Correct 13 ms 23936 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23892 KB n=100
17 Correct 13 ms 23940 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 16 ms 23944 KB n=100
20 Correct 13 ms 23936 KB n=100
21 Correct 14 ms 23972 KB n=100
22 Correct 13 ms 23892 KB n=100
23 Correct 14 ms 23932 KB n=100
24 Correct 13 ms 23940 KB n=100
25 Correct 13 ms 23868 KB n=100
26 Correct 13 ms 23936 KB n=12
27 Correct 13 ms 24000 KB n=100
28 Correct 13 ms 24020 KB n=500
29 Correct 14 ms 24132 KB n=500
30 Correct 15 ms 24076 KB n=500
31 Correct 18 ms 24128 KB n=500
32 Correct 17 ms 24020 KB n=500
33 Correct 14 ms 24092 KB n=500
34 Correct 13 ms 24020 KB n=500
35 Incorrect 16 ms 24072 KB Wrong range.
36 Halted 0 ms 0 KB -

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 15 ms 23960 KB n=100
3 Correct 13 ms 24000 KB n=100
4 Correct 12 ms 23988 KB n=100
5 Correct 13 ms 23892 KB n=100
6 Correct 13 ms 23940 KB n=100
7 Correct 12 ms 23940 KB n=100
8 Correct 14 ms 23948 KB n=100
9 Correct 14 ms 23932 KB n=100
10 Correct 14 ms 23936 KB n=100
11 Correct 12 ms 23944 KB n=100
12 Correct 13 ms 23892 KB n=100
13 Correct 13 ms 24020 KB n=100
14 Correct 13 ms 23936 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23892 KB n=100
17 Correct 13 ms 23940 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 16 ms 23944 KB n=100
20 Correct 13 ms 23936 KB n=100
21 Correct 14 ms 23972 KB n=100
22 Correct 13 ms 23892 KB n=100
23 Correct 14 ms 23932 KB n=100
24 Correct 13 ms 23940 KB n=100
25 Correct 13 ms 23868 KB n=100
26 Correct 13 ms 23936 KB n=12
27 Correct 13 ms 24000 KB n=100
28 Correct 13 ms 24020 KB n=500
29 Correct 14 ms 24132 KB n=500
30 Correct 15 ms 24076 KB n=500
31 Correct 18 ms 24128 KB n=500
32 Correct 17 ms 24020 KB n=500
33 Correct 14 ms 24092 KB n=500
34 Correct 13 ms 24020 KB n=500
35 Incorrect 16 ms 24072 KB Wrong range.
36 Halted 0 ms 0 KB -