oj.uz

Submission #682406

# Submission time Handle Problem Language Result Execution time Memory
682406 2023-01-16T08:11:20 Z phoenix Birthday gift (IZhO18_treearray) C++17
100 / 100
 1087 ms 84780 KB 
#include<bits/stdc++.h>
 
using namespace std;
const int N = 200000 + 100;
int n, m, q;
int anc[ N ][ 19 ];
vector<int> g[ N ];
int tin[ N ], tout[ N ];
 
int timer;
set<int> dd[ N ], ss[ N ];
 
void DFS(int s,int p = 1) {
    tin[ s ] = ++timer;
    anc[ s ][ 0 ] = p;
    for(int i = 1;i < 19;i++)
        anc[ s ][ i ] = anc[anc[ s ][i - 1]][i - 1];
 
    for(int to : g[ s ]) {
        if(to != p)
            DFS(to, s);
    }
    tout[ s ] = ++timer;
}
 
bool isAncestor(int a, int b) {
    return (tin[ a ] <= tin[ b ] && tout[ a ] >= tout[ b ]);
}
int lca(int a, int b) {
    if(isAncestor(a, b)) return a;
    if(isAncestor(b, a)) return b;
    for(int i = 18;i >= 0;i--)
        if(!isAncestor(anc[ a ][ i ], b))
            a = anc[ a ][ i ];
    return anc[ a ][ 0 ];
}
pair<int,int> f(set<int> &s, int l, int r, int cc) {
    if(l > r || s.empty() || *s.begin() > r || *(--s.end()) < l) return {-1, -1};
    auto it = s.lower_bound( l );
    if(*it > r) return {-1, -1};
    return {*it, *it + cc};
}
int main() {
    ios::sync_with_stdio( 0 );
    cin.tie( 0 );
    cout.tie( 0 );
    cin >> n >> m >> q;
    int a[m + 1], t[ m ];
    for(int i = 1;i < n;i++) {
        int u, v;
        cin >> u >> v;
        g[ u ].push_back( v );
        g[ v ].push_back( u );
    }
    DFS( 1 );
    for(int i = 1;i <= m;i++) {
        cin >> a[ i ];
        ss[ a[ i ] ].insert( i );
    }
    for(int i = 1;i < m;i++) {
        t[ i ] = lca(a[ i ], a[i + 1]);
        dd[ t[ i ] ].insert( i );
    }
 
    while(q--) {
        int type;
        cin >> type;
        if(type == 1) {
            int pos, v;
            cin >> pos >> v;
            ss[ a[ pos ] ].erase( pos );
            ss[ v ].insert( pos );
            a[ pos ] = v;
            if(pos < m) {
                dd[ t[ pos ] ].erase( pos );
                t[ pos ] = lca(a[ pos ], a[pos + 1]) ;
                dd[ t[ pos ] ].insert( pos );
            }
            if(pos > 1) {
                dd[ t[pos - 1] ].erase(pos - 1);
                t[pos - 1] = lca(a[pos - 1], a[ pos ]);
                dd[ t[pos - 1] ].insert(pos - 1);
            }
        } else {
            int l, r, u;
            cin >> l >> r >> u;
            pair<int,int> res1 = f(ss[ u ], l, r, 0), res2 = f(dd[ u ], l, r - 1, 1);
            if(res1 != make_pair(-1, -1)) cout << res1.first << ' ' << res1.second << '\n';
            else cout << res2.first << ' ' << res2.second << '\n';
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB n=5
2 Correct 13 ms 23768 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23924 KB n=100
6 Correct 15 ms 23836 KB n=100
7 Correct 13 ms 23792 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23832 KB n=100
12 Correct 14 ms 23840 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 14 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 16 ms 23840 KB n=100
17 Correct 15 ms 23840 KB n=100
18 Correct 16 ms 23764 KB n=100
19 Correct 14 ms 23832 KB n=100
20 Correct 14 ms 23764 KB n=100
21 Correct 14 ms 23828 KB n=100
22 Correct 15 ms 23764 KB n=100
23 Correct 14 ms 23748 KB n=100
24 Correct 17 ms 23800 KB n=100
25 Correct 16 ms 23796 KB n=100
26 Correct 12 ms 23732 KB n=12
27 Correct 13 ms 23764 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB n=5
2 Correct 13 ms 23768 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23924 KB n=100
6 Correct 15 ms 23836 KB n=100
7 Correct 13 ms 23792 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23832 KB n=100
12 Correct 14 ms 23840 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 14 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 16 ms 23840 KB n=100
17 Correct 15 ms 23840 KB n=100
18 Correct 16 ms 23764 KB n=100
19 Correct 14 ms 23832 KB n=100
20 Correct 14 ms 23764 KB n=100
21 Correct 14 ms 23828 KB n=100
22 Correct 15 ms 23764 KB n=100
23 Correct 14 ms 23748 KB n=100
24 Correct 17 ms 23800 KB n=100
25 Correct 16 ms 23796 KB n=100
26 Correct 12 ms 23732 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 14 ms 23840 KB n=500
29 Correct 15 ms 23976 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23924 KB n=500
32 Correct 13 ms 23868 KB n=500
33 Correct 17 ms 23844 KB n=500
34 Correct 15 ms 23900 KB n=500
35 Correct 13 ms 23920 KB n=500
36 Correct 13 ms 23892 KB n=500
37 Correct 13 ms 23884 KB n=500
38 Correct 13 ms 23892 KB n=500
39 Correct 13 ms 23908 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 13 ms 23844 KB n=500
42 Correct 14 ms 23952 KB n=500
43 Correct 13 ms 23900 KB n=500
44 Correct 17 ms 23892 KB n=500
45 Correct 15 ms 23892 KB n=500
46 Correct 13 ms 23984 KB n=500
47 Correct 13 ms 23884 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 14 ms 23892 KB n=500
50 Correct 13 ms 23852 KB n=500
51 Correct 14 ms 23840 KB n=500
52 Correct 14 ms 23892 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 14 ms 23892 KB n=500
55 Correct 15 ms 23836 KB n=278
56 Correct 16 ms 23968 KB n=500
57 Correct 14 ms 23892 KB n=500
58 Correct 14 ms 23892 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB n=5
2 Correct 13 ms 23768 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23924 KB n=100
6 Correct 15 ms 23836 KB n=100
7 Correct 13 ms 23792 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23832 KB n=100
12 Correct 14 ms 23840 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 14 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 16 ms 23840 KB n=100
17 Correct 15 ms 23840 KB n=100
18 Correct 16 ms 23764 KB n=100
19 Correct 14 ms 23832 KB n=100
20 Correct 14 ms 23764 KB n=100
21 Correct 14 ms 23828 KB n=100
22 Correct 15 ms 23764 KB n=100
23 Correct 14 ms 23748 KB n=100
24 Correct 17 ms 23800 KB n=100
25 Correct 16 ms 23796 KB n=100
26 Correct 12 ms 23732 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 14 ms 23840 KB n=500
29 Correct 15 ms 23976 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23924 KB n=500
32 Correct 13 ms 23868 KB n=500
33 Correct 17 ms 23844 KB n=500
34 Correct 15 ms 23900 KB n=500
35 Correct 13 ms 23920 KB n=500
36 Correct 13 ms 23892 KB n=500
37 Correct 13 ms 23884 KB n=500
38 Correct 13 ms 23892 KB n=500
39 Correct 13 ms 23908 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 13 ms 23844 KB n=500
42 Correct 14 ms 23952 KB n=500
43 Correct 13 ms 23900 KB n=500
44 Correct 17 ms 23892 KB n=500
45 Correct 15 ms 23892 KB n=500
46 Correct 13 ms 23984 KB n=500
47 Correct 13 ms 23884 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 14 ms 23892 KB n=500
50 Correct 13 ms 23852 KB n=500
51 Correct 14 ms 23840 KB n=500
52 Correct 14 ms 23892 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 14 ms 23892 KB n=500
55 Correct 15 ms 23836 KB n=278
56 Correct 16 ms 23968 KB n=500
57 Correct 14 ms 23892 KB n=500
58 Correct 14 ms 23892 KB n=500
59 Correct 16 ms 24288 KB n=2000
60 Correct 15 ms 24360 KB n=2000
61 Correct 15 ms 24280 KB n=2000
62 Correct 15 ms 24276 KB n=2000
63 Correct 16 ms 24276 KB n=2000
64 Correct 15 ms 24276 KB n=2000
65 Correct 16 ms 24208 KB n=2000
66 Correct 14 ms 24276 KB n=2000
67 Correct 15 ms 24276 KB n=2000
68 Correct 16 ms 24356 KB n=2000
69 Correct 16 ms 24228 KB n=2000
70 Correct 15 ms 24308 KB n=2000
71 Correct 16 ms 24316 KB n=2000
72 Correct 15 ms 24276 KB n=2000
73 Correct 16 ms 24336 KB n=2000
74 Correct 16 ms 24276 KB n=1844
75 Correct 16 ms 24276 KB n=2000
76 Correct 17 ms 24308 KB n=2000
77 Correct 19 ms 24220 KB n=2000
78 Correct 15 ms 24312 KB n=2000
79 Correct 16 ms 24276 KB n=2000
80 Correct 15 ms 24392 KB n=2000
81 Correct 15 ms 24364 KB n=2000
82 Correct 17 ms 24224 KB n=2000
83 Correct 17 ms 24352 KB n=2000
84 Correct 15 ms 24228 KB n=2000
85 Correct 16 ms 24360 KB n=2000
86 Correct 16 ms 24276 KB n=2000
87 Correct 15 ms 24276 KB n=2000
88 Correct 15 ms 24404 KB n=2000
89 Correct 17 ms 24348 KB n=2000
90 Correct 14 ms 24404 KB n=2000
91 Correct 14 ms 24224 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23900 KB n=5
2 Correct 13 ms 23768 KB n=100
3 Correct 12 ms 23764 KB n=100
4 Correct 13 ms 23764 KB n=100
5 Correct 14 ms 23924 KB n=100
6 Correct 15 ms 23836 KB n=100
7 Correct 13 ms 23792 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23828 KB n=100
10 Correct 12 ms 23764 KB n=100
11 Correct 13 ms 23832 KB n=100
12 Correct 14 ms 23840 KB n=100
13 Correct 13 ms 23764 KB n=100
14 Correct 14 ms 23764 KB n=100
15 Correct 14 ms 23764 KB n=100
16 Correct 16 ms 23840 KB n=100
17 Correct 15 ms 23840 KB n=100
18 Correct 16 ms 23764 KB n=100
19 Correct 14 ms 23832 KB n=100
20 Correct 14 ms 23764 KB n=100
21 Correct 14 ms 23828 KB n=100
22 Correct 15 ms 23764 KB n=100
23 Correct 14 ms 23748 KB n=100
24 Correct 17 ms 23800 KB n=100
25 Correct 16 ms 23796 KB n=100
26 Correct 12 ms 23732 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 14 ms 23840 KB n=500
29 Correct 15 ms 23976 KB n=500
30 Correct 13 ms 23892 KB n=500
31 Correct 13 ms 23924 KB n=500
32 Correct 13 ms 23868 KB n=500
33 Correct 17 ms 23844 KB n=500
34 Correct 15 ms 23900 KB n=500
35 Correct 13 ms 23920 KB n=500
36 Correct 13 ms 23892 KB n=500
37 Correct 13 ms 23884 KB n=500
38 Correct 13 ms 23892 KB n=500
39 Correct 13 ms 23908 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 13 ms 23844 KB n=500
42 Correct 14 ms 23952 KB n=500
43 Correct 13 ms 23900 KB n=500
44 Correct 17 ms 23892 KB n=500
45 Correct 15 ms 23892 KB n=500
46 Correct 13 ms 23984 KB n=500
47 Correct 13 ms 23884 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 14 ms 23892 KB n=500
50 Correct 13 ms 23852 KB n=500
51 Correct 14 ms 23840 KB n=500
52 Correct 14 ms 23892 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 14 ms 23892 KB n=500
55 Correct 15 ms 23836 KB n=278
56 Correct 16 ms 23968 KB n=500
57 Correct 14 ms 23892 KB n=500
58 Correct 14 ms 23892 KB n=500
59 Correct 16 ms 24288 KB n=2000
60 Correct 15 ms 24360 KB n=2000
61 Correct 15 ms 24280 KB n=2000
62 Correct 15 ms 24276 KB n=2000
63 Correct 16 ms 24276 KB n=2000
64 Correct 15 ms 24276 KB n=2000
65 Correct 16 ms 24208 KB n=2000
66 Correct 14 ms 24276 KB n=2000
67 Correct 15 ms 24276 KB n=2000
68 Correct 16 ms 24356 KB n=2000
69 Correct 16 ms 24228 KB n=2000
70 Correct 15 ms 24308 KB n=2000
71 Correct 16 ms 24316 KB n=2000
72 Correct 15 ms 24276 KB n=2000
73 Correct 16 ms 24336 KB n=2000
74 Correct 16 ms 24276 KB n=1844
75 Correct 16 ms 24276 KB n=2000
76 Correct 17 ms 24308 KB n=2000
77 Correct 19 ms 24220 KB n=2000
78 Correct 15 ms 24312 KB n=2000
79 Correct 16 ms 24276 KB n=2000
80 Correct 15 ms 24392 KB n=2000
81 Correct 15 ms 24364 KB n=2000
82 Correct 17 ms 24224 KB n=2000
83 Correct 17 ms 24352 KB n=2000
84 Correct 15 ms 24228 KB n=2000
85 Correct 16 ms 24360 KB n=2000
86 Correct 16 ms 24276 KB n=2000
87 Correct 15 ms 24276 KB n=2000
88 Correct 15 ms 24404 KB n=2000
89 Correct 17 ms 24348 KB n=2000
90 Correct 14 ms 24404 KB n=2000
91 Correct 14 ms 24224 KB n=2000
92 Correct 613 ms 75476 KB n=200000
93 Correct 686 ms 80216 KB n=200000
94 Correct 632 ms 83532 KB n=200000
95 Correct 657 ms 75132 KB n=200000
96 Correct 701 ms 75180 KB n=200000
97 Correct 778 ms 79320 KB n=200000
98 Correct 641 ms 75340 KB n=200000
99 Correct 774 ms 75332 KB n=200000
100 Correct 699 ms 75260 KB n=200000
101 Correct 555 ms 84780 KB n=200000
102 Correct 415 ms 76316 KB n=200000
103 Correct 445 ms 76284 KB n=200000
104 Correct 492 ms 76296 KB n=200000
105 Correct 439 ms 76912 KB n=200000
106 Correct 537 ms 76712 KB n=200000
107 Correct 413 ms 76856 KB n=200000
108 Correct 772 ms 75192 KB n=200000
109 Correct 739 ms 75256 KB n=200000
110 Correct 795 ms 75332 KB n=200000
111 Correct 843 ms 74620 KB n=200000
112 Correct 579 ms 83756 KB n=200000
113 Correct 813 ms 79312 KB n=200000
114 Correct 811 ms 74696 KB n=200000
115 Correct 1087 ms 77284 KB n=200000
116 Correct 701 ms 75344 KB n=200000
117 Correct 560 ms 84200 KB n=200000
118 Correct 867 ms 78164 KB n=200000
119 Correct 639 ms 75328 KB n=200000
120 Correct 639 ms 83808 KB n=200000
121 Correct 585 ms 83828 KB n=200000
122 Correct 509 ms 84204 KB n=200000
123 Correct 502 ms 76472 KB n=200000
124 Correct 193 ms 39040 KB n=25264