oj.uz

Submission #865719

# Submission time Handle Problem Language Result Execution time Memory
865719 2023-10-24T14:42:48 Z vjudge1 Birthday gift (IZhO18_treearray) C++17
100 / 100
 697 ms 88800 KB 
/// tree bends in youth
/// 24  .10.2023
/// success is doing same thing in every single day!!!
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) x.begin(), x.end()
#define F first
#define S second
using namespace std;
const ll N =2e5+ 5;
const ll NN =2e6 + 5;
const ll INF = -1e1;
const ll MOD = 1e9 + 7;
const ll LG = 18;
const ll k = 316;
vector <int> g[N];
int cnt;
int tin[N],tout[N],used[N],p[N][20],a[N];
set <int> d[N],b[N];
void dfs(int v){
    cnt++;
    tin[v] = cnt;
    used[v] = 1;
    for(int to : g[v]){
        if(used[to] == 0){
            p[to][0] = v;
            dfs(to);
        }
    }
    tout[v] = cnt;
}
bool upper(int x,int y){
    if(tin[x] <= tin[y] && tout[x] >= tout[y])return 1;
    return 0;
}
int lca(int x,int y){
    if(upper(x,y) == 1){
        return x;
    }
    if(upper(y,x) == 1){
        return y;
    }
    for(int i = 18;i >= 0;i--){
        int h = p[x][i];
        if(upper(h,y) == 0){
            x = h;
        }
    }
    return p[x][0];
}
void solve(){
    int n,m,q;
    cin >> n >> m >> q;
    for(int i = 1;i <n ;i++){
        int u,v;cin>>u>>v;
        g[u].pb(v),g[v].pb(u);
    }
    p[1][0] = 1;
    dfs(1);
    for(int i = 1;i <= 18;i++){
        for(int j = 1;j <= n;j++){
            p[j][i] = p[p[j][i - 1]][i - 1];
        }
    }
    for(int i= 1;i <= m;i++){
        cin >> a[i];
        b[a[i]].insert(i);
        if(i > 1){
            d[lca(a[i],a[i - 1])].insert(i - 1);
        }
    }
    while(q--){
        int tp,l,r,v;cin >> tp;
        if(tp == 1){
            cin >> l >> r;
            b[a[l]].erase(l);
            if(l > 1)d[lca(a[l - 1],a[l])].erase(l - 1);
            if(l < m)d[lca(a[l + 1],a[l])].erase(l);
            a[l] = r;
            if(l > 1)d[lca(a[l - 1],a[l])].insert(l - 1);
            if(l < m)d[lca(a[l + 1],a[l])].insert(l);
            b[a[l]].insert(l);
        }
        else{
            cin >> l >>r  >> v;
            if(d[v].lower_bound(l) != d[v].end() && *d[v].lower_bound(l) < r){
                int x = *d[v].lower_bound(l);
                cout << x << ' ' << x + 1 << '\n';
            }
            else if(b[v].lower_bound(l) != b[v].end() && *b[v].lower_bound(l) <= r){
                int x = *b[v].lower_bound(l);
                cout << x << ' ' << x << '\n';
            }
            else{
                cout << "-1 -1\n";
            }
        }
    }
}
main (){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
//    freopen("input.txt","r",stdin);
//    freopen("output.txt","w",stdout);
    ll abd= 1;
//    cin >> abd;
    for(ll i = 1;i <= abd;i++){
//        cout << "Case " << i << ":\n";
        solve();
    }
}
//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


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

Compilation message

treearray.cpp:101:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  101 | main (){
      | ^~~~

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28252 KB n=5
2 Correct 6 ms 28252 KB n=100
3 Correct 6 ms 28252 KB n=100
4 Correct 6 ms 28252 KB n=100
5 Correct 6 ms 28248 KB n=100
6 Correct 6 ms 28252 KB n=100
7 Correct 6 ms 28252 KB n=100
8 Correct 6 ms 28252 KB n=100
9 Correct 5 ms 28248 KB n=100
10 Correct 6 ms 28252 KB n=100
11 Correct 6 ms 28252 KB n=100
12 Correct 5 ms 28248 KB n=100
13 Correct 6 ms 28252 KB n=100
14 Correct 6 ms 28252 KB n=100
15 Correct 6 ms 28252 KB n=100
16 Correct 6 ms 28252 KB n=100
17 Correct 6 ms 28248 KB n=100
18 Correct 6 ms 28252 KB n=100
19 Correct 5 ms 28252 KB n=100
20 Correct 6 ms 28252 KB n=100
21 Correct 6 ms 28320 KB n=100
22 Correct 5 ms 28252 KB n=100
23 Correct 6 ms 28252 KB n=100
24 Correct 6 ms 28252 KB n=100
25 Correct 6 ms 28252 KB n=100
26 Correct 6 ms 28248 KB n=12
27 Correct 6 ms 28252 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 28252 KB n=5
2 Correct 6 ms 28252 KB n=100
3 Correct 6 ms 28252 KB n=100
4 Correct 6 ms 28252 KB n=100
5 Correct 6 ms 28248 KB n=100
6 Correct 6 ms 28252 KB n=100
7 Correct 6 ms 28252 KB n=100
8 Correct 6 ms 28252 KB n=100
9 Correct 5 ms 28248 KB n=100
10 Correct 6 ms 28252 KB n=100
11 Correct 6 ms 28252 KB n=100
12 Correct 5 ms 28248 KB n=100
13 Correct 6 ms 28252 KB n=100
14 Correct 6 ms 28252 KB n=100
15 Correct 6 ms 28252 KB n=100
16 Correct 6 ms 28252 KB n=100
17 Correct 6 ms 28248 KB n=100
18 Correct 6 ms 28252 KB n=100
19 Correct 5 ms 28252 KB n=100
20 Correct 6 ms 28252 KB n=100
21 Correct 6 ms 28320 KB n=100
22 Correct 5 ms 28252 KB n=100
23 Correct 6 ms 28252 KB n=100
24 Correct 6 ms 28252 KB n=100
25 Correct 6 ms 28252 KB n=100
26 Correct 6 ms 28248 KB n=12
27 Correct 6 ms 28252 KB n=100
28 Correct 6 ms 28252 KB n=500
29 Correct 6 ms 28268 KB n=500
30 Correct 6 ms 28376 KB n=500
31 Correct 6 ms 28252 KB n=500
32 Correct 6 ms 28320 KB n=500
33 Correct 7 ms 28252 KB n=500
34 Correct 6 ms 28248 KB n=500
35 Correct 6 ms 28376 KB n=500
36 Correct 6 ms 28252 KB n=500
37 Correct 6 ms 28252 KB n=500
38 Correct 6 ms 28252 KB n=500
39 Correct 6 ms 28252 KB n=500
40 Correct 6 ms 28248 KB n=500
41 Correct 6 ms 28252 KB n=500
42 Correct 6 ms 28252 KB n=500
43 Correct 6 ms 28500 KB n=500
44 Correct 6 ms 28440 KB n=500
45 Correct 6 ms 28248 KB n=500
46 Correct 6 ms 28252 KB n=500
47 Correct 6 ms 28248 KB n=500
48 Correct 6 ms 28248 KB n=500
49 Correct 6 ms 28252 KB n=500
50 Correct 6 ms 28248 KB n=500
51 Correct 7 ms 28248 KB n=500
52 Correct 7 ms 28252 KB n=500
53 Correct 6 ms 28252 KB n=500
54 Correct 6 ms 28248 KB n=500
55 Correct 6 ms 28252 KB n=278
56 Correct 6 ms 28252 KB n=500
57 Correct 6 ms 28252 KB n=500
58 Correct 7 ms 28252 KB n=500
59 Correct 10 ms 28764 KB n=2000
60 Correct 8 ms 28764 KB n=2000
61 Correct 8 ms 28504 KB n=2000
62 Correct 9 ms 28512 KB n=2000
63 Correct 8 ms 28508 KB n=2000
64 Correct 8 ms 28516 KB n=2000
65 Correct 8 ms 28508 KB n=2000
66 Correct 8 ms 28764 KB n=2000
67 Correct 9 ms 28508 KB n=2000
68 Correct 8 ms 28572 KB n=2000
69 Correct 8 ms 28508 KB n=2000
70 Correct 8 ms 28504 KB n=2000
71 Correct 7 ms 28508 KB n=2000
72 Correct 8 ms 28508 KB n=2000
73 Correct 8 ms 28508 KB n=2000
74 Correct 8 ms 28508 KB n=1844
75 Correct 7 ms 28504 KB n=2000
76 Correct 9 ms 28504 KB n=2000
77 Correct 8 ms 28760 KB n=2000
78 Correct 8 ms 28508 KB n=2000
79 Correct 9 ms 28508 KB n=2000
80 Correct 8 ms 28628 KB n=2000
81 Correct 8 ms 28508 KB n=2000
82 Correct 8 ms 28508 KB n=2000
83 Correct 8 ms 28508 KB n=2000
84 Correct 8 ms 28504 KB n=2000
85 Correct 8 ms 28508 KB n=2000
86 Correct 8 ms 28504 KB n=2000
87 Correct 8 ms 28508 KB n=2000
88 Correct 7 ms 28764 KB n=2000
89 Correct 7 ms 28764 KB n=2000
90 Correct 8 ms 28764 KB n=2000
91 Correct 8 ms 28504 KB n=2000
92 Correct 587 ms 75352 KB n=200000
93 Correct 612 ms 82516 KB n=200000
94 Correct 461 ms 87028 KB n=200000
95 Correct 585 ms 76080 KB n=200000
96 Correct 582 ms 75868 KB n=200000
97 Correct 655 ms 81372 KB n=200000
98 Correct 588 ms 75968 KB n=200000
99 Correct 661 ms 76028 KB n=200000
100 Correct 606 ms 76084 KB n=200000
101 Correct 427 ms 88800 KB n=200000
102 Correct 352 ms 77136 KB n=200000
103 Correct 350 ms 77140 KB n=200000
104 Correct 351 ms 77132 KB n=200000
105 Correct 354 ms 77652 KB n=200000
106 Correct 331 ms 77648 KB n=200000
107 Correct 340 ms 77304 KB n=200000
108 Correct 624 ms 76108 KB n=200000
109 Correct 635 ms 76352 KB n=200000
110 Correct 643 ms 76356 KB n=200000
111 Correct 622 ms 75984 KB n=200000
112 Correct 413 ms 87396 KB n=200000
113 Correct 583 ms 81492 KB n=200000
114 Correct 524 ms 75460 KB n=200000
115 Correct 697 ms 78416 KB n=200000
116 Correct 494 ms 76396 KB n=200000
117 Correct 360 ms 88000 KB n=200000
118 Correct 636 ms 79952 KB n=200000
119 Correct 482 ms 76212 KB n=200000
120 Correct 330 ms 87640 KB n=200000
121 Correct 306 ms 87636 KB n=200000
122 Correct 341 ms 88184 KB n=200000
123 Correct 299 ms 77516 KB n=200000
124 Correct 89 ms 43088 KB n=25264