oj.uz

Submission #835375

# Submission time Handle Problem Language Result Execution time Memory
835375 2023-08-23T13:54:58 Z dimashhh Birthday gift (IZhO18_treearray) C++17
100 / 100
 772 ms 85492 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int N = 2e5 + 1,MOD = 998244353;

int n,m,q,a[N],up[N][20],tin[N],tout[N],timer = 0,b[N];
vector<int> g[N];
set<int> t[N],f[N];
int ans;
void dfs(int v,int pr = 1){
    tin[v] = ++timer;
    up[v][0] = pr;
    for(int i = 1;i <= 18;i++){
        up[v][i] = up[up[v][i - 1]][i - 1];
    }
    for(int to:g[v]){
        if(to != pr) dfs(to,v);
    }
    tout[v] = timer;
}
bool is(int v,int u){
    return (tin[v] <= tin[u] && tout[v] >= tout[u]);
}
int lca(int v,int u){
    if(is(v,u)) return v;
    if(is(u,v)) return u;
    for(int i = 18;i >= 0;i--){
        if(!is(up[v][i],u)){
            v = up[v][i];
        }
    }
    return up[v][0];
}
void test(){
    cin >> n >> m >> q;
    for(int i = 1;i <= n - 1;i++){
        int x,y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    for(int i = 1;i <= m;i++){
        cin >> a[i];
        t[a[i]].insert(i);
        if(i > 1) b[i - 1] = lca(a[i - 1],a[i]);
        f[b[i - 1]].insert(i - 1);
    }
    while(q--){
        int tp;
        cin >> tp;
        if(tp == 1){
            int pos,v;
            cin >> pos >> v;
            t[a[pos]].erase(pos);
            if(pos < m){
                int x = lca(v,a[pos + 1]);
                f[b[pos]].erase(pos);
                b[pos] = x;
                f[b[pos]].insert(pos);
            }
            if(pos > 1){
                int x = lca(a[pos - 1],v);
                f[b[pos - 1]].erase(pos - 1);                
                b[pos - 1] = x;
                f[b[pos - 1]].insert(pos - 1);                
            }
            a[pos] = v;
            t[a[pos]].insert(pos);
        }else{
            int l,r,v;
            cin >> l >> r >> v;
            if(l == r){
                if(v == a[l]){
                    cout << l << ' ' << r << '\n';
                }else{
                    cout << -1 << ' ' << -1 << '\n';
                }
                continue;
            }
            auto it = f[v].lower_bound(l);
            if(it != f[v].end() && *it < r){
                cout << *it << ' ' << *it + 1 << '\n'; 
            }else{
                auto it = t[v].lower_bound(l);
                if(it != t[v].end() && *it <= r){
                    cout << *it << ' ' << *it << '\n';
                    continue;
                }
                cout << -1 << ' ' << -1 << '\n';
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int t = 1;
    //cin >> t;
    while(t--) test();
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23720 KB n=5
2 Correct 12 ms 23748 KB n=100
3 Correct 14 ms 23844 KB n=100
4 Correct 14 ms 23792 KB n=100
5 Correct 13 ms 23816 KB n=100
6 Correct 12 ms 23812 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 15 ms 23784 KB n=100
9 Correct 14 ms 23852 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 13 ms 23848 KB n=100
13 Correct 14 ms 23760 KB n=100
14 Correct 15 ms 23764 KB n=100
15 Correct 15 ms 23840 KB n=100
16 Correct 13 ms 23780 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 15 ms 23808 KB n=100
19 Correct 12 ms 23732 KB n=100
20 Correct 14 ms 23808 KB n=100
21 Correct 16 ms 23836 KB n=100
22 Correct 12 ms 23828 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 12 ms 23764 KB n=100
25 Correct 15 ms 23812 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 13 ms 23844 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23720 KB n=5
2 Correct 12 ms 23748 KB n=100
3 Correct 14 ms 23844 KB n=100
4 Correct 14 ms 23792 KB n=100
5 Correct 13 ms 23816 KB n=100
6 Correct 12 ms 23812 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 15 ms 23784 KB n=100
9 Correct 14 ms 23852 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 13 ms 23848 KB n=100
13 Correct 14 ms 23760 KB n=100
14 Correct 15 ms 23764 KB n=100
15 Correct 15 ms 23840 KB n=100
16 Correct 13 ms 23780 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 15 ms 23808 KB n=100
19 Correct 12 ms 23732 KB n=100
20 Correct 14 ms 23808 KB n=100
21 Correct 16 ms 23836 KB n=100
22 Correct 12 ms 23828 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 12 ms 23764 KB n=100
25 Correct 15 ms 23812 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 13 ms 23844 KB n=100
28 Correct 13 ms 23892 KB n=500
29 Correct 13 ms 23980 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23940 KB n=500
32 Correct 15 ms 23892 KB n=500
33 Correct 12 ms 23892 KB n=500
34 Correct 11 ms 23948 KB n=500
35 Correct 12 ms 23948 KB n=500
36 Correct 11 ms 23924 KB n=500
37 Correct 11 ms 23892 KB n=500
38 Correct 11 ms 23904 KB n=500
39 Correct 11 ms 23892 KB n=500
40 Correct 12 ms 23840 KB n=500
41 Correct 12 ms 23892 KB n=500
42 Correct 11 ms 23944 KB n=500
43 Correct 12 ms 23892 KB n=500
44 Correct 13 ms 23856 KB n=500
45 Correct 13 ms 23836 KB n=500
46 Correct 12 ms 23956 KB n=500
47 Correct 12 ms 23892 KB n=500
48 Correct 11 ms 23892 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 19 ms 23952 KB n=500
51 Correct 12 ms 23892 KB n=500
52 Correct 13 ms 23960 KB n=500
53 Correct 12 ms 23952 KB n=500
54 Correct 14 ms 23908 KB n=500
55 Correct 12 ms 23812 KB n=278
56 Correct 12 ms 23892 KB n=500
57 Correct 13 ms 23948 KB n=500
58 Correct 15 ms 23824 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23720 KB n=5
2 Correct 12 ms 23748 KB n=100
3 Correct 14 ms 23844 KB n=100
4 Correct 14 ms 23792 KB n=100
5 Correct 13 ms 23816 KB n=100
6 Correct 12 ms 23812 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 15 ms 23784 KB n=100
9 Correct 14 ms 23852 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 13 ms 23848 KB n=100
13 Correct 14 ms 23760 KB n=100
14 Correct 15 ms 23764 KB n=100
15 Correct 15 ms 23840 KB n=100
16 Correct 13 ms 23780 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 15 ms 23808 KB n=100
19 Correct 12 ms 23732 KB n=100
20 Correct 14 ms 23808 KB n=100
21 Correct 16 ms 23836 KB n=100
22 Correct 12 ms 23828 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 12 ms 23764 KB n=100
25 Correct 15 ms 23812 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 13 ms 23844 KB n=100
28 Correct 13 ms 23892 KB n=500
29 Correct 13 ms 23980 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23940 KB n=500
32 Correct 15 ms 23892 KB n=500
33 Correct 12 ms 23892 KB n=500
34 Correct 11 ms 23948 KB n=500
35 Correct 12 ms 23948 KB n=500
36 Correct 11 ms 23924 KB n=500
37 Correct 11 ms 23892 KB n=500
38 Correct 11 ms 23904 KB n=500
39 Correct 11 ms 23892 KB n=500
40 Correct 12 ms 23840 KB n=500
41 Correct 12 ms 23892 KB n=500
42 Correct 11 ms 23944 KB n=500
43 Correct 12 ms 23892 KB n=500
44 Correct 13 ms 23856 KB n=500
45 Correct 13 ms 23836 KB n=500
46 Correct 12 ms 23956 KB n=500
47 Correct 12 ms 23892 KB n=500
48 Correct 11 ms 23892 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 19 ms 23952 KB n=500
51 Correct 12 ms 23892 KB n=500
52 Correct 13 ms 23960 KB n=500
53 Correct 12 ms 23952 KB n=500
54 Correct 14 ms 23908 KB n=500
55 Correct 12 ms 23812 KB n=278
56 Correct 12 ms 23892 KB n=500
57 Correct 13 ms 23948 KB n=500
58 Correct 15 ms 23824 KB n=500
59 Correct 15 ms 24308 KB n=2000
60 Correct 14 ms 24404 KB n=2000
61 Correct 15 ms 24292 KB n=2000
62 Correct 14 ms 24320 KB n=2000
63 Correct 15 ms 24276 KB n=2000
64 Correct 15 ms 24276 KB n=2000
65 Correct 17 ms 24244 KB n=2000
66 Correct 15 ms 24292 KB n=2000
67 Correct 16 ms 24276 KB n=2000
68 Correct 14 ms 24312 KB n=2000
69 Correct 14 ms 24276 KB n=2000
70 Correct 14 ms 24276 KB n=2000
71 Correct 15 ms 24340 KB n=2000
72 Correct 18 ms 24284 KB n=2000
73 Correct 17 ms 24404 KB n=2000
74 Correct 15 ms 24276 KB n=1844
75 Correct 15 ms 24340 KB n=2000
76 Correct 15 ms 24336 KB n=2000
77 Correct 15 ms 24296 KB n=2000
78 Correct 14 ms 24276 KB n=2000
79 Correct 16 ms 24200 KB n=2000
80 Correct 14 ms 24332 KB n=2000
81 Correct 18 ms 24336 KB n=2000
82 Correct 15 ms 24224 KB n=2000
83 Correct 18 ms 24276 KB n=2000
84 Correct 19 ms 24352 KB n=2000
85 Correct 15 ms 24276 KB n=2000
86 Correct 15 ms 24320 KB n=2000
87 Correct 14 ms 24292 KB n=2000
88 Correct 14 ms 24404 KB n=2000
89 Correct 16 ms 24404 KB n=2000
90 Correct 14 ms 24336 KB n=2000
91 Correct 18 ms 24276 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23720 KB n=5
2 Correct 12 ms 23748 KB n=100
3 Correct 14 ms 23844 KB n=100
4 Correct 14 ms 23792 KB n=100
5 Correct 13 ms 23816 KB n=100
6 Correct 12 ms 23812 KB n=100
7 Correct 12 ms 23808 KB n=100
8 Correct 15 ms 23784 KB n=100
9 Correct 14 ms 23852 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 13 ms 23848 KB n=100
13 Correct 14 ms 23760 KB n=100
14 Correct 15 ms 23764 KB n=100
15 Correct 15 ms 23840 KB n=100
16 Correct 13 ms 23780 KB n=100
17 Correct 12 ms 23764 KB n=100
18 Correct 15 ms 23808 KB n=100
19 Correct 12 ms 23732 KB n=100
20 Correct 14 ms 23808 KB n=100
21 Correct 16 ms 23836 KB n=100
22 Correct 12 ms 23828 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 12 ms 23764 KB n=100
25 Correct 15 ms 23812 KB n=100
26 Correct 13 ms 23764 KB n=12
27 Correct 13 ms 23844 KB n=100
28 Correct 13 ms 23892 KB n=500
29 Correct 13 ms 23980 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23940 KB n=500
32 Correct 15 ms 23892 KB n=500
33 Correct 12 ms 23892 KB n=500
34 Correct 11 ms 23948 KB n=500
35 Correct 12 ms 23948 KB n=500
36 Correct 11 ms 23924 KB n=500
37 Correct 11 ms 23892 KB n=500
38 Correct 11 ms 23904 KB n=500
39 Correct 11 ms 23892 KB n=500
40 Correct 12 ms 23840 KB n=500
41 Correct 12 ms 23892 KB n=500
42 Correct 11 ms 23944 KB n=500
43 Correct 12 ms 23892 KB n=500
44 Correct 13 ms 23856 KB n=500
45 Correct 13 ms 23836 KB n=500
46 Correct 12 ms 23956 KB n=500
47 Correct 12 ms 23892 KB n=500
48 Correct 11 ms 23892 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 19 ms 23952 KB n=500
51 Correct 12 ms 23892 KB n=500
52 Correct 13 ms 23960 KB n=500
53 Correct 12 ms 23952 KB n=500
54 Correct 14 ms 23908 KB n=500
55 Correct 12 ms 23812 KB n=278
56 Correct 12 ms 23892 KB n=500
57 Correct 13 ms 23948 KB n=500
58 Correct 15 ms 23824 KB n=500
59 Correct 15 ms 24308 KB n=2000
60 Correct 14 ms 24404 KB n=2000
61 Correct 15 ms 24292 KB n=2000
62 Correct 14 ms 24320 KB n=2000
63 Correct 15 ms 24276 KB n=2000
64 Correct 15 ms 24276 KB n=2000
65 Correct 17 ms 24244 KB n=2000
66 Correct 15 ms 24292 KB n=2000
67 Correct 16 ms 24276 KB n=2000
68 Correct 14 ms 24312 KB n=2000
69 Correct 14 ms 24276 KB n=2000
70 Correct 14 ms 24276 KB n=2000
71 Correct 15 ms 24340 KB n=2000
72 Correct 18 ms 24284 KB n=2000
73 Correct 17 ms 24404 KB n=2000
74 Correct 15 ms 24276 KB n=1844
75 Correct 15 ms 24340 KB n=2000
76 Correct 15 ms 24336 KB n=2000
77 Correct 15 ms 24296 KB n=2000
78 Correct 14 ms 24276 KB n=2000
79 Correct 16 ms 24200 KB n=2000
80 Correct 14 ms 24332 KB n=2000
81 Correct 18 ms 24336 KB n=2000
82 Correct 15 ms 24224 KB n=2000
83 Correct 18 ms 24276 KB n=2000
84 Correct 19 ms 24352 KB n=2000
85 Correct 15 ms 24276 KB n=2000
86 Correct 15 ms 24320 KB n=2000
87 Correct 14 ms 24292 KB n=2000
88 Correct 14 ms 24404 KB n=2000
89 Correct 16 ms 24404 KB n=2000
90 Correct 14 ms 24336 KB n=2000
91 Correct 18 ms 24276 KB n=2000
92 Correct 607 ms 76104 KB n=200000
93 Correct 666 ms 80908 KB n=200000
94 Correct 494 ms 84424 KB n=200000
95 Correct 582 ms 75852 KB n=200000
96 Correct 584 ms 75880 KB n=200000
97 Correct 656 ms 80044 KB n=200000
98 Correct 599 ms 75816 KB n=200000
99 Correct 696 ms 76052 KB n=200000
100 Correct 626 ms 75956 KB n=200000
101 Correct 448 ms 85492 KB n=200000
102 Correct 379 ms 77036 KB n=200000
103 Correct 388 ms 77220 KB n=200000
104 Correct 360 ms 77232 KB n=200000
105 Correct 368 ms 77560 KB n=200000
106 Correct 389 ms 77544 KB n=200000
107 Correct 362 ms 77560 KB n=200000
108 Correct 634 ms 76028 KB n=200000
109 Correct 625 ms 75996 KB n=200000
110 Correct 637 ms 76036 KB n=200000
111 Correct 593 ms 75352 KB n=200000
112 Correct 453 ms 84616 KB n=200000
113 Correct 629 ms 79948 KB n=200000
114 Correct 623 ms 75512 KB n=200000
115 Correct 772 ms 77976 KB n=200000
116 Correct 557 ms 76104 KB n=200000
117 Correct 431 ms 84948 KB n=200000
118 Correct 699 ms 78848 KB n=200000
119 Correct 625 ms 75980 KB n=200000
120 Correct 387 ms 84508 KB n=200000
121 Correct 424 ms 84556 KB n=200000
122 Correct 399 ms 84852 KB n=200000
123 Correct 392 ms 77264 KB n=200000
124 Correct 142 ms 39232 KB n=25264