oj.uz

Submission #343716

# Submission time Handle Problem Language Result Execution time Memory
343716 2021-01-04T12:17:02 Z Sprdalo Birthday gift (IZhO18_treearray) C++17
100 / 100
 1626 ms 96632 KB 
#include <bits/stdc++.h>

using namespace std;

#define int ll
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<double> vd;
typedef vector<bool> vb;
typedef vector<char> vc;
typedef vector<string> vs;
typedef vector<pi> vp;
typedef vector<pl> vpl;

const int maxn = 200010;
vector<vi> p(19, vi(maxn, -1));
vi e[maxn];
vp t(maxn);
int tim;
 
void root(int x){
    for (int i : e[x]){
        if (p[0][x] == i) continue;
        p[0][i] = x;
        root(i);
    }
}

void dfs(int x){
    ++tim;
    int r = p[0][x];
    for (int i = 1; i < 19 && r > -1; ++i){
        p[i][x] = p[i - 1][r];
        r = p[i - 1][r];
    }
 
    t[x].first = tim;
    for (auto& i : e[x]){
        dfs(i);
    }
    t[x].second = tim;
}
 
int ok(int x, int y){
    if (t[x].first <= t[y].first && t[y].second <= t[x].second)
        return x;
    swap(x, y); 
    if (t[x].first <= t[y].first && t[y].second <= t[x].second)
        return x;
 
    return 0;
}

int lca(int x, int y){
    int z = ok(x, y);

    if (z){
        return z;
    }

    for (int i = 18; i > -1; --i){
        int tmp = p[i][x];
        if (tmp == -1 || ok(tmp, y)) continue;
        x = tmp;
    }

    return p[0][x];
}

set<int> s[maxn], d[maxn];
vi a;
int m;

void dodaj(int pos){
    s[a[pos]].insert(pos);
    if (pos < m){ 
        int k = lca(a[pos], a[pos+1]);
        d[k].insert(pos);
    }

    if (pos>1){
        int k = lca(a[pos], a[pos-1]);
        d[k].insert(pos-1);
    }
}

void brisi(int pos){
    s[a[pos]].erase(pos);
    if (pos < m){
        int k = lca(a[pos], a[pos+1]);
        d[k].erase(pos);
    }

    if (pos > 1){
        int k = lca(a[pos-1], a[pos]);
        d[k].erase(pos-1);
    }
}

signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    

    int n, q;
    cin >> n >> m >> q;

    for (int i = 0; i < n - 1; ++i){
        int u, v;
        cin >> u >> v;

        e[u].push_back(v);
        e[v].push_back(u);
    }

    root(1);

    for (int i = 1; i <= n; ++i){
        e[i].clear();
    }

    for (int i = 2; i <= n; ++i){
        e[p[0][i]].push_back(i);
    }

    dfs(1);

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

    for (int i = 1; i <= m; ++i){
        dodaj(i);
    }

    for (int h = 0; h < q; ++h){
        int z;
        cin >> z;

        if (z == 1){
            int pos, val;
            cin >> pos >> val;

            brisi(pos);
            a[pos] = val;
            dodaj(pos);

            continue;
        }

        int l, r, x;
        cin >> l >> r >> x;

        auto it = s[x].lower_bound(l);
        if (it != s[x].end()){
            int ind = *it;
            if (ind <= r){
                cout << ind << ' ' << ind << '\n';
                continue;
            }
        }

        it = d[x].lower_bound(l);
        if (it != d[x].end()){
            int ind = *it;
            if (ind < r){
                cout << ind << ' ' << ind+1 << '\n';
                continue;
            }
        }

        cout << "-1 -1\n";
    }
}
/*
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
*/

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56784 KB n=5
2 Correct 34 ms 56784 KB n=100
3 Correct 35 ms 56784 KB n=100
4 Correct 40 ms 56784 KB n=100
5 Correct 40 ms 56784 KB n=100
6 Correct 38 ms 56784 KB n=100
7 Correct 33 ms 56784 KB n=100
8 Correct 34 ms 56784 KB n=100
9 Correct 34 ms 56784 KB n=100
10 Correct 33 ms 56784 KB n=100
11 Correct 35 ms 56784 KB n=100
12 Correct 34 ms 56784 KB n=100
13 Correct 34 ms 56784 KB n=100
14 Correct 34 ms 56784 KB n=100
15 Correct 33 ms 56784 KB n=100
16 Correct 34 ms 56784 KB n=100
17 Correct 34 ms 56784 KB n=100
18 Correct 40 ms 56784 KB n=100
19 Correct 38 ms 56784 KB n=100
20 Correct 35 ms 56784 KB n=100
21 Correct 34 ms 56784 KB n=100
22 Correct 36 ms 56784 KB n=100
23 Correct 35 ms 56784 KB n=100
24 Correct 34 ms 56784 KB n=100
25 Correct 34 ms 56784 KB n=100
26 Correct 34 ms 56780 KB n=12
27 Correct 36 ms 56784 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 56784 KB n=5
2 Correct 34 ms 56784 KB n=100
3 Correct 35 ms 56784 KB n=100
4 Correct 40 ms 56784 KB n=100
5 Correct 40 ms 56784 KB n=100
6 Correct 38 ms 56784 KB n=100
7 Correct 33 ms 56784 KB n=100
8 Correct 34 ms 56784 KB n=100
9 Correct 34 ms 56784 KB n=100
10 Correct 33 ms 56784 KB n=100
11 Correct 35 ms 56784 KB n=100
12 Correct 34 ms 56784 KB n=100
13 Correct 34 ms 56784 KB n=100
14 Correct 34 ms 56784 KB n=100
15 Correct 33 ms 56784 KB n=100
16 Correct 34 ms 56784 KB n=100
17 Correct 34 ms 56784 KB n=100
18 Correct 40 ms 56784 KB n=100
19 Correct 38 ms 56784 KB n=100
20 Correct 35 ms 56784 KB n=100
21 Correct 34 ms 56784 KB n=100
22 Correct 36 ms 56784 KB n=100
23 Correct 35 ms 56784 KB n=100
24 Correct 34 ms 56784 KB n=100
25 Correct 34 ms 56784 KB n=100
26 Correct 34 ms 56780 KB n=12
27 Correct 36 ms 56784 KB n=100
28 Correct 35 ms 56784 KB n=500
29 Correct 35 ms 56784 KB n=500
30 Correct 34 ms 56784 KB n=500
31 Correct 34 ms 56784 KB n=500
32 Correct 34 ms 56784 KB n=500
33 Correct 36 ms 56784 KB n=500
34 Correct 35 ms 56784 KB n=500
35 Correct 34 ms 56784 KB n=500
36 Correct 36 ms 56784 KB n=500
37 Correct 34 ms 56784 KB n=500
38 Correct 34 ms 56912 KB n=500
39 Correct 35 ms 56784 KB n=500
40 Correct 35 ms 56784 KB n=500
41 Correct 34 ms 56784 KB n=500
42 Correct 36 ms 56912 KB n=500
43 Correct 34 ms 56784 KB n=500
44 Correct 35 ms 56784 KB n=500
45 Correct 35 ms 56784 KB n=500
46 Correct 34 ms 56784 KB n=500
47 Correct 34 ms 56784 KB n=500
48 Correct 34 ms 56784 KB n=500
49 Correct 34 ms 56784 KB n=500
50 Correct 34 ms 56784 KB n=500
51 Correct 34 ms 56784 KB n=500
52 Correct 37 ms 56784 KB n=500
53 Correct 37 ms 56784 KB n=500
54 Correct 34 ms 56784 KB n=500
55 Correct 34 ms 56784 KB n=278
56 Correct 35 ms 56784 KB n=500
57 Correct 34 ms 56784 KB n=500
58 Correct 34 ms 56784 KB n=500
59 Correct 38 ms 57168 KB n=2000
60 Correct 38 ms 57168 KB n=2000
61 Correct 39 ms 57168 KB n=2000
62 Correct 38 ms 57040 KB n=2000
63 Correct 38 ms 57040 KB n=2000
64 Correct 37 ms 57168 KB n=2000
65 Correct 39 ms 57040 KB n=2000
66 Correct 44 ms 57168 KB n=2000
67 Correct 41 ms 57208 KB n=2000
68 Correct 39 ms 57040 KB n=2000
69 Correct 43 ms 57040 KB n=2000
70 Correct 37 ms 57040 KB n=2000
71 Correct 38 ms 57040 KB n=2000
72 Correct 37 ms 57188 KB n=2000
73 Correct 37 ms 57040 KB n=2000
74 Correct 38 ms 57040 KB n=1844
75 Correct 38 ms 57040 KB n=2000
76 Correct 37 ms 57040 KB n=2000
77 Correct 39 ms 57040 KB n=2000
78 Correct 38 ms 57040 KB n=2000
79 Correct 37 ms 57040 KB n=2000
80 Correct 38 ms 57168 KB n=2000
81 Correct 38 ms 57168 KB n=2000
82 Correct 37 ms 57040 KB n=2000
83 Correct 37 ms 57168 KB n=2000
84 Correct 37 ms 57040 KB n=2000
85 Correct 38 ms 57040 KB n=2000
86 Correct 38 ms 57040 KB n=2000
87 Correct 38 ms 57040 KB n=2000
88 Correct 41 ms 57168 KB n=2000
89 Correct 37 ms 57168 KB n=2000
90 Correct 38 ms 57168 KB n=2000
91 Correct 37 ms 57040 KB n=2000
92 Correct 1024 ms 88272 KB n=200000
93 Correct 1178 ms 91940 KB n=200000
94 Correct 767 ms 95056 KB n=200000
95 Correct 955 ms 88032 KB n=200000
96 Correct 913 ms 88064 KB n=200000
97 Correct 1282 ms 90912 KB n=200000
98 Correct 946 ms 88016 KB n=200000
99 Correct 1123 ms 87760 KB n=200000
100 Correct 978 ms 88188 KB n=200000
101 Correct 662 ms 95824 KB n=200000
102 Correct 604 ms 89168 KB n=200000
103 Correct 684 ms 89168 KB n=200000
104 Correct 617 ms 89204 KB n=200000
105 Correct 601 ms 88956 KB n=200000
106 Correct 657 ms 88932 KB n=200000
107 Correct 602 ms 89168 KB n=200000
108 Correct 1055 ms 88036 KB n=200000
109 Correct 1153 ms 87888 KB n=200000
110 Correct 1072 ms 87888 KB n=200000
111 Correct 967 ms 88100 KB n=200000
112 Correct 731 ms 95056 KB n=200000
113 Correct 1251 ms 91132 KB n=200000
114 Correct 952 ms 88144 KB n=200000
115 Correct 1626 ms 89084 KB n=200000
116 Correct 943 ms 88000 KB n=200000
117 Correct 738 ms 95292 KB n=200000
118 Correct 1567 ms 90044 KB n=200000
119 Correct 1004 ms 88224 KB n=200000
120 Correct 664 ms 95824 KB n=200000
121 Correct 651 ms 95824 KB n=200000
122 Correct 689 ms 96632 KB n=200000
123 Correct 647 ms 89324 KB n=200000
124 Correct 249 ms 69456 KB n=25264