oj.uz

Submission #541281

# Submission time Handle Problem Language Result Execution time Memory
541281 2022-03-22T22:04:16 Z Tadiorn Birthday gift (IZhO18_treearray) C++14
100 / 100
 1642 ms 83244 KB 
#include <bits/stdc++.h>
#define fi first
#define se second
#define ll long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define INF 1000000000
#define LINF 1000000000000000000
#define pb push_back
#define MAXN 200010
#define LGN 18
using namespace std;

vector<int> a[MAXN];
int val[MAXN];
set<int> indeksi[MAXN];
set<int> indeksi2[MAXN];
int st[LGN][MAXN];
int in[MAXN], out[MAXN];
int T;

void dfs(int s, int p){
    in[s] = ++T;
    st[0][s] = p;
    for(auto x : a[s]){
        if(x != p){
            dfs(x, s);
        }
    }
    out[s] = ++T;
}

void init(int n){
    for(int lg = 1; lg < LGN; lg++){
        for(int i = 0; i < n; i++){
            st[lg][i] = st[lg-1][st[lg-1][i]];
        }
    }
}

bool UinV(int u, int v){ /// da li je cvor U u podstablu cvora V
    if(in[v] <= in[u] && out[u] <= out[v]) return true;
    return false;
}

int lca(int u, int v){
    if(UinV(u, v)) return v;
    if(UinV(v, u)) return u;
    int tr = u;
    for(int lg = LGN-1; lg >= 0; lg--){
        //cout << lg << ": ";
        if(!UinV(v, st[lg][tr])){
            //cout << "usao";
            tr = st[lg][tr];
        } //cout << endl;
    }

    return st[0][tr];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int n, m, q;
    cin >> n >> m >> q;
    for(int i = 0; i < n-1; i++){
        int u, v; cin >> u >> v; u--; v--;
        a[u].pb(v); a[v].pb(u);
    }
    dfs(0, 0);
    init(n);
    /*for(int i = 0; i < n; i++){
        cout << i+1 << ": ";
        for(int j = 0; j < LGN; j++) cout << st[j][i]+1 << " ";
        cout << endl;
    }*/
    /*while(true){
        cout << "START" << endl;
        int u, v; cin >> u >> v; u--, v--;
        cout << lca(u, v)+1 << endl;
    }*/
    for(int i = 0; i < m; i++){
        cin >> val[i]; val[i]--;
        indeksi2[val[i]].insert(i);
    }
    for(int i = 1; i < m; i++){
        indeksi[lca(val[i-1], val[i])].insert(i-1);
    }
    /*cout << "===" << endl;
    for(int i = 0; i < n; i++){
        cout << i+1 << ": ";
        for(auto x : indeksi[i]){
            cout << x + 1 << " ";
        } cout << endl;
    }
    cout << "---" << endl;*/
    while(q--){
        int t; cin >> t;
        if(t == 1){
            int idx, v; cin >> idx >> v; idx--; v--;
            if(idx >= 1){
                indeksi[lca(val[idx-1], val[idx])].erase(idx-1);
                indeksi[lca(val[idx-1], v)].insert(idx-1);
            }
            if(idx < m-1){
                indeksi[lca(val[idx], val[idx+1])].erase(idx);
                indeksi[lca(v, val[idx+1])].insert(idx);
            }
            indeksi2[val[idx]].erase(idx);
            indeksi2[v].insert(idx);
            val[idx] = v;
            /*for(int i = 0; i < m; i++) cout << val[i] + 1 << " ";
            cout << endl;
            cout << "===" << endl;
            for(int i = 0; i < n; i++){
                cout << i+1 << ": ";
                for(auto x : indeksi[i]){
                    cout << x + 1 << " ";
                } cout << endl;
            }
            cout << "---" << endl;*/
        }
        else{
            int l, r, v; cin >> l >> r >> v; l--, v--, r--;
            auto it2 = indeksi2[v].lower_bound(l);
            if(it2 != indeksi2[v].end() && *it2 <= r){cout << *it2+1 << " " << *it2+1 << endl; continue;}
            auto it = indeksi[v].lower_bound(l);
            if(it == indeksi[v].end()) cout << "-1 -1" << endl;
            else if(*it + 1 <= r) cout << *it + 1 << " " << *it+2 << endl;
            else cout << "-1 -1" << endl;
        }
    }

    return 0;
}



/**
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1

8 7 7
1 2
3 1
3 4
5 3
6 2
4 7
8 4
4 5 2 3 8 8 7
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
1 6 1
1 4 4
2 3 7 3




*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 12 ms 23892 KB n=100
3 Correct 17 ms 23892 KB n=100
4 Correct 15 ms 23952 KB n=100
5 Correct 13 ms 23952 KB n=100
6 Correct 12 ms 23860 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 13 ms 23944 KB n=100
9 Correct 16 ms 23892 KB n=100
10 Correct 13 ms 23892 KB n=100
11 Correct 14 ms 23892 KB n=100
12 Correct 13 ms 23948 KB n=100
13 Correct 12 ms 23948 KB n=100
14 Correct 13 ms 23948 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23948 KB n=100
17 Correct 14 ms 23848 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 13 ms 23948 KB n=100
20 Correct 13 ms 23940 KB n=100
21 Correct 12 ms 23876 KB n=100
22 Correct 14 ms 23892 KB n=100
23 Correct 13 ms 23892 KB n=100
24 Correct 13 ms 23832 KB n=100
25 Correct 13 ms 23892 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 14 ms 23952 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 12 ms 23892 KB n=100
3 Correct 17 ms 23892 KB n=100
4 Correct 15 ms 23952 KB n=100
5 Correct 13 ms 23952 KB n=100
6 Correct 12 ms 23860 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 13 ms 23944 KB n=100
9 Correct 16 ms 23892 KB n=100
10 Correct 13 ms 23892 KB n=100
11 Correct 14 ms 23892 KB n=100
12 Correct 13 ms 23948 KB n=100
13 Correct 12 ms 23948 KB n=100
14 Correct 13 ms 23948 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23948 KB n=100
17 Correct 14 ms 23848 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 13 ms 23948 KB n=100
20 Correct 13 ms 23940 KB n=100
21 Correct 12 ms 23876 KB n=100
22 Correct 14 ms 23892 KB n=100
23 Correct 13 ms 23892 KB n=100
24 Correct 13 ms 23832 KB n=100
25 Correct 13 ms 23892 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 14 ms 23952 KB n=100
28 Correct 13 ms 24032 KB n=500
29 Correct 14 ms 23992 KB n=500
30 Correct 13 ms 23964 KB n=500
31 Correct 14 ms 23964 KB n=500
32 Correct 14 ms 24020 KB n=500
33 Correct 17 ms 23964 KB n=500
34 Correct 14 ms 24020 KB n=500
35 Correct 13 ms 24056 KB n=500
36 Correct 14 ms 24020 KB n=500
37 Correct 15 ms 23948 KB n=500
38 Correct 14 ms 24052 KB n=500
39 Correct 14 ms 23964 KB n=500
40 Correct 13 ms 24020 KB n=500
41 Correct 18 ms 24020 KB n=500
42 Correct 16 ms 24148 KB n=500
43 Correct 14 ms 24020 KB n=500
44 Correct 14 ms 23984 KB n=500
45 Correct 14 ms 24064 KB n=500
46 Correct 13 ms 24020 KB n=500
47 Correct 13 ms 24020 KB n=500
48 Correct 14 ms 23988 KB n=500
49 Correct 17 ms 23964 KB n=500
50 Correct 15 ms 24020 KB n=500
51 Correct 13 ms 24020 KB n=500
52 Correct 13 ms 23968 KB n=500
53 Correct 13 ms 24020 KB n=500
54 Correct 13 ms 24020 KB n=500
55 Correct 13 ms 24012 KB n=278
56 Correct 14 ms 23956 KB n=500
57 Correct 14 ms 24020 KB n=500
58 Correct 17 ms 23976 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 12 ms 23892 KB n=100
3 Correct 17 ms 23892 KB n=100
4 Correct 15 ms 23952 KB n=100
5 Correct 13 ms 23952 KB n=100
6 Correct 12 ms 23860 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 13 ms 23944 KB n=100
9 Correct 16 ms 23892 KB n=100
10 Correct 13 ms 23892 KB n=100
11 Correct 14 ms 23892 KB n=100
12 Correct 13 ms 23948 KB n=100
13 Correct 12 ms 23948 KB n=100
14 Correct 13 ms 23948 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23948 KB n=100
17 Correct 14 ms 23848 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 13 ms 23948 KB n=100
20 Correct 13 ms 23940 KB n=100
21 Correct 12 ms 23876 KB n=100
22 Correct 14 ms 23892 KB n=100
23 Correct 13 ms 23892 KB n=100
24 Correct 13 ms 23832 KB n=100
25 Correct 13 ms 23892 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 14 ms 23952 KB n=100
28 Correct 13 ms 24032 KB n=500
29 Correct 14 ms 23992 KB n=500
30 Correct 13 ms 23964 KB n=500
31 Correct 14 ms 23964 KB n=500
32 Correct 14 ms 24020 KB n=500
33 Correct 17 ms 23964 KB n=500
34 Correct 14 ms 24020 KB n=500
35 Correct 13 ms 24056 KB n=500
36 Correct 14 ms 24020 KB n=500
37 Correct 15 ms 23948 KB n=500
38 Correct 14 ms 24052 KB n=500
39 Correct 14 ms 23964 KB n=500
40 Correct 13 ms 24020 KB n=500
41 Correct 18 ms 24020 KB n=500
42 Correct 16 ms 24148 KB n=500
43 Correct 14 ms 24020 KB n=500
44 Correct 14 ms 23984 KB n=500
45 Correct 14 ms 24064 KB n=500
46 Correct 13 ms 24020 KB n=500
47 Correct 13 ms 24020 KB n=500
48 Correct 14 ms 23988 KB n=500
49 Correct 17 ms 23964 KB n=500
50 Correct 15 ms 24020 KB n=500
51 Correct 13 ms 24020 KB n=500
52 Correct 13 ms 23968 KB n=500
53 Correct 13 ms 24020 KB n=500
54 Correct 13 ms 24020 KB n=500
55 Correct 13 ms 24012 KB n=278
56 Correct 14 ms 23956 KB n=500
57 Correct 14 ms 24020 KB n=500
58 Correct 17 ms 23976 KB n=500
59 Correct 21 ms 24404 KB n=2000
60 Correct 16 ms 24404 KB n=2000
61 Correct 16 ms 24420 KB n=2000
62 Correct 20 ms 24328 KB n=2000
63 Correct 19 ms 24404 KB n=2000
64 Correct 18 ms 24420 KB n=2000
65 Correct 20 ms 24324 KB n=2000
66 Correct 17 ms 24348 KB n=2000
67 Correct 17 ms 24404 KB n=2000
68 Correct 17 ms 24424 KB n=2000
69 Correct 18 ms 24284 KB n=2000
70 Correct 18 ms 24404 KB n=2000
71 Correct 19 ms 24336 KB n=2000
72 Correct 20 ms 24376 KB n=2000
73 Correct 17 ms 24348 KB n=2000
74 Correct 17 ms 24368 KB n=1844
75 Correct 18 ms 24404 KB n=2000
76 Correct 16 ms 24352 KB n=2000
77 Correct 22 ms 24404 KB n=2000
78 Correct 18 ms 24348 KB n=2000
79 Correct 18 ms 24332 KB n=2000
80 Correct 16 ms 24404 KB n=2000
81 Correct 17 ms 24404 KB n=2000
82 Correct 18 ms 24404 KB n=2000
83 Correct 17 ms 24432 KB n=2000
84 Correct 17 ms 24352 KB n=2000
85 Correct 18 ms 24396 KB n=2000
86 Correct 19 ms 24308 KB n=2000
87 Correct 17 ms 24392 KB n=2000
88 Correct 16 ms 24472 KB n=2000
89 Correct 17 ms 24404 KB n=2000
90 Correct 17 ms 24472 KB n=2000
91 Correct 21 ms 24396 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB n=5
2 Correct 12 ms 23892 KB n=100
3 Correct 17 ms 23892 KB n=100
4 Correct 15 ms 23952 KB n=100
5 Correct 13 ms 23952 KB n=100
6 Correct 12 ms 23860 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 13 ms 23944 KB n=100
9 Correct 16 ms 23892 KB n=100
10 Correct 13 ms 23892 KB n=100
11 Correct 14 ms 23892 KB n=100
12 Correct 13 ms 23948 KB n=100
13 Correct 12 ms 23948 KB n=100
14 Correct 13 ms 23948 KB n=100
15 Correct 13 ms 23892 KB n=100
16 Correct 13 ms 23948 KB n=100
17 Correct 14 ms 23848 KB n=100
18 Correct 13 ms 23892 KB n=100
19 Correct 13 ms 23948 KB n=100
20 Correct 13 ms 23940 KB n=100
21 Correct 12 ms 23876 KB n=100
22 Correct 14 ms 23892 KB n=100
23 Correct 13 ms 23892 KB n=100
24 Correct 13 ms 23832 KB n=100
25 Correct 13 ms 23892 KB n=100
26 Correct 13 ms 23892 KB n=12
27 Correct 14 ms 23952 KB n=100
28 Correct 13 ms 24032 KB n=500
29 Correct 14 ms 23992 KB n=500
30 Correct 13 ms 23964 KB n=500
31 Correct 14 ms 23964 KB n=500
32 Correct 14 ms 24020 KB n=500
33 Correct 17 ms 23964 KB n=500
34 Correct 14 ms 24020 KB n=500
35 Correct 13 ms 24056 KB n=500
36 Correct 14 ms 24020 KB n=500
37 Correct 15 ms 23948 KB n=500
38 Correct 14 ms 24052 KB n=500
39 Correct 14 ms 23964 KB n=500
40 Correct 13 ms 24020 KB n=500
41 Correct 18 ms 24020 KB n=500
42 Correct 16 ms 24148 KB n=500
43 Correct 14 ms 24020 KB n=500
44 Correct 14 ms 23984 KB n=500
45 Correct 14 ms 24064 KB n=500
46 Correct 13 ms 24020 KB n=500
47 Correct 13 ms 24020 KB n=500
48 Correct 14 ms 23988 KB n=500
49 Correct 17 ms 23964 KB n=500
50 Correct 15 ms 24020 KB n=500
51 Correct 13 ms 24020 KB n=500
52 Correct 13 ms 23968 KB n=500
53 Correct 13 ms 24020 KB n=500
54 Correct 13 ms 24020 KB n=500
55 Correct 13 ms 24012 KB n=278
56 Correct 14 ms 23956 KB n=500
57 Correct 14 ms 24020 KB n=500
58 Correct 17 ms 23976 KB n=500
59 Correct 21 ms 24404 KB n=2000
60 Correct 16 ms 24404 KB n=2000
61 Correct 16 ms 24420 KB n=2000
62 Correct 20 ms 24328 KB n=2000
63 Correct 19 ms 24404 KB n=2000
64 Correct 18 ms 24420 KB n=2000
65 Correct 20 ms 24324 KB n=2000
66 Correct 17 ms 24348 KB n=2000
67 Correct 17 ms 24404 KB n=2000
68 Correct 17 ms 24424 KB n=2000
69 Correct 18 ms 24284 KB n=2000
70 Correct 18 ms 24404 KB n=2000
71 Correct 19 ms 24336 KB n=2000
72 Correct 20 ms 24376 KB n=2000
73 Correct 17 ms 24348 KB n=2000
74 Correct 17 ms 24368 KB n=1844
75 Correct 18 ms 24404 KB n=2000
76 Correct 16 ms 24352 KB n=2000
77 Correct 22 ms 24404 KB n=2000
78 Correct 18 ms 24348 KB n=2000
79 Correct 18 ms 24332 KB n=2000
80 Correct 16 ms 24404 KB n=2000
81 Correct 17 ms 24404 KB n=2000
82 Correct 18 ms 24404 KB n=2000
83 Correct 17 ms 24432 KB n=2000
84 Correct 17 ms 24352 KB n=2000
85 Correct 18 ms 24396 KB n=2000
86 Correct 19 ms 24308 KB n=2000
87 Correct 17 ms 24392 KB n=2000
88 Correct 16 ms 24472 KB n=2000
89 Correct 17 ms 24404 KB n=2000
90 Correct 17 ms 24472 KB n=2000
91 Correct 21 ms 24396 KB n=2000
92 Correct 1589 ms 73808 KB n=200000
93 Correct 1196 ms 78732 KB n=200000
94 Correct 752 ms 81900 KB n=200000
95 Correct 1642 ms 73492 KB n=200000
96 Correct 1612 ms 73636 KB n=200000
97 Correct 1269 ms 77796 KB n=200000
98 Correct 1569 ms 73644 KB n=200000
99 Correct 1596 ms 73804 KB n=200000
100 Correct 1621 ms 73676 KB n=200000
101 Correct 643 ms 83244 KB n=200000
102 Correct 824 ms 74788 KB n=200000
103 Correct 882 ms 74792 KB n=200000
104 Correct 809 ms 74784 KB n=200000
105 Correct 818 ms 75168 KB n=200000
106 Correct 790 ms 75092 KB n=200000
107 Correct 820 ms 75304 KB n=200000
108 Correct 1382 ms 73604 KB n=200000
109 Correct 1426 ms 73600 KB n=200000
110 Correct 1407 ms 73668 KB n=200000
111 Correct 1342 ms 73204 KB n=200000
112 Correct 685 ms 82140 KB n=200000
113 Correct 1180 ms 77704 KB n=200000
114 Correct 1407 ms 73292 KB n=200000
115 Correct 1530 ms 75656 KB n=200000
116 Correct 1497 ms 73804 KB n=200000
117 Correct 624 ms 82556 KB n=200000
118 Correct 1338 ms 76488 KB n=200000
119 Correct 1402 ms 73792 KB n=200000
120 Correct 539 ms 82184 KB n=200000
121 Correct 527 ms 82256 KB n=200000
122 Correct 539 ms 82508 KB n=200000
123 Correct 778 ms 75168 KB n=200000
124 Correct 200 ms 38708 KB n=25264