oj.uz

Submission #680422

# Submission time Handle Problem Language Result Execution time Memory
680422 2023-01-10T18:53:33 Z phoenix Birthday gift (IZhO18_treearray) C++17
56 / 100
 818 ms 84844 KB 
#include<bits/stdc++.h>

using namespace std;
const int N = 200001;
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, bool cc) {
    if(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 < n) {
                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 23764 KB n=5
2 Correct 11 ms 23764 KB n=100
3 Correct 12 ms 23824 KB n=100
4 Correct 15 ms 23784 KB n=100
5 Correct 12 ms 23736 KB n=100
6 Correct 14 ms 23892 KB n=100
7 Correct 11 ms 23736 KB n=100
8 Correct 11 ms 23764 KB n=100
9 Correct 12 ms 23736 KB n=100
10 Correct 12 ms 23820 KB n=100
11 Correct 11 ms 23764 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 14 ms 23812 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23816 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 13 ms 23848 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 13 ms 23812 KB n=100
24 Correct 12 ms 23820 KB n=100
25 Correct 12 ms 23764 KB n=100
26 Correct 12 ms 23828 KB n=12
27 Correct 12 ms 23820 KB n=100

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 11 ms 23764 KB n=100
3 Correct 12 ms 23824 KB n=100
4 Correct 15 ms 23784 KB n=100
5 Correct 12 ms 23736 KB n=100
6 Correct 14 ms 23892 KB n=100
7 Correct 11 ms 23736 KB n=100
8 Correct 11 ms 23764 KB n=100
9 Correct 12 ms 23736 KB n=100
10 Correct 12 ms 23820 KB n=100
11 Correct 11 ms 23764 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 14 ms 23812 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23816 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 13 ms 23848 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 13 ms 23812 KB n=100
24 Correct 12 ms 23820 KB n=100
25 Correct 12 ms 23764 KB n=100
26 Correct 12 ms 23828 KB n=12
27 Correct 12 ms 23820 KB n=100
28 Correct 12 ms 23836 KB n=500
29 Correct 12 ms 23948 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 13 ms 23960 KB n=500
32 Correct 16 ms 23832 KB n=500
33 Correct 13 ms 23940 KB n=500
34 Correct 13 ms 23836 KB n=500
35 Correct 12 ms 23892 KB n=500
36 Correct 12 ms 23892 KB n=500
37 Correct 12 ms 23892 KB n=500
38 Correct 13 ms 23892 KB n=500
39 Correct 13 ms 23892 KB n=500
40 Correct 13 ms 23836 KB n=500
41 Correct 13 ms 23852 KB n=500
42 Correct 12 ms 23912 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 12 ms 23892 KB n=500
45 Correct 13 ms 23952 KB n=500
46 Correct 15 ms 23892 KB n=500
47 Correct 13 ms 23892 KB n=500
48 Correct 12 ms 23908 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 12 ms 23892 KB n=500
51 Correct 12 ms 23892 KB n=500
52 Correct 12 ms 23888 KB n=500
53 Correct 13 ms 23836 KB n=500
54 Correct 13 ms 23892 KB n=500
55 Correct 12 ms 23824 KB n=278
56 Correct 13 ms 23892 KB n=500
57 Correct 12 ms 23960 KB n=500
58 Correct 13 ms 23836 KB n=500
59 Correct 16 ms 24276 KB n=2000
60 Correct 15 ms 24404 KB n=2000
61 Correct 15 ms 24324 KB n=2000
62 Correct 15 ms 24276 KB n=2000
63 Correct 18 ms 24276 KB n=2000
64 Correct 15 ms 24312 KB n=2000
65 Correct 15 ms 24316 KB n=2000
66 Correct 14 ms 24280 KB n=2000
67 Correct 15 ms 24276 KB n=2000
68 Correct 15 ms 24276 KB n=2000
69 Correct 14 ms 24276 KB n=2000
70 Correct 15 ms 24312 KB n=2000
71 Correct 18 ms 24276 KB n=2000
72 Correct 15 ms 24184 KB n=2000
73 Correct 14 ms 24264 KB n=2000
74 Correct 15 ms 24284 KB n=1844
75 Correct 14 ms 24216 KB n=2000
76 Correct 14 ms 24276 KB n=2000
77 Correct 18 ms 24308 KB n=2000
78 Correct 18 ms 24276 KB n=2000
79 Correct 14 ms 24276 KB n=2000
80 Correct 14 ms 24276 KB n=2000
81 Correct 14 ms 24356 KB n=2000
82 Correct 15 ms 24268 KB n=2000
83 Correct 19 ms 24404 KB n=2000
84 Correct 16 ms 24268 KB n=2000
85 Correct 16 ms 24276 KB n=2000
86 Correct 15 ms 24348 KB n=2000
87 Correct 15 ms 24216 KB n=2000
88 Correct 15 ms 24344 KB n=2000
89 Correct 15 ms 24308 KB n=2000
90 Correct 15 ms 24352 KB n=2000
91 Correct 16 ms 24268 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23764 KB n=5
2 Correct 11 ms 23764 KB n=100
3 Correct 12 ms 23824 KB n=100
4 Correct 15 ms 23784 KB n=100
5 Correct 12 ms 23736 KB n=100
6 Correct 14 ms 23892 KB n=100
7 Correct 11 ms 23736 KB n=100
8 Correct 11 ms 23764 KB n=100
9 Correct 12 ms 23736 KB n=100
10 Correct 12 ms 23820 KB n=100
11 Correct 11 ms 23764 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 14 ms 23812 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 12 ms 23816 KB n=100
16 Correct 12 ms 23764 KB n=100
17 Correct 12 ms 23816 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 12 ms 23820 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 13 ms 23848 KB n=100
22 Correct 12 ms 23764 KB n=100
23 Correct 13 ms 23812 KB n=100
24 Correct 12 ms 23820 KB n=100
25 Correct 12 ms 23764 KB n=100
26 Correct 12 ms 23828 KB n=12
27 Correct 12 ms 23820 KB n=100
28 Correct 12 ms 23836 KB n=500
29 Correct 12 ms 23948 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 13 ms 23960 KB n=500
32 Correct 16 ms 23832 KB n=500
33 Correct 13 ms 23940 KB n=500
34 Correct 13 ms 23836 KB n=500
35 Correct 12 ms 23892 KB n=500
36 Correct 12 ms 23892 KB n=500
37 Correct 12 ms 23892 KB n=500
38 Correct 13 ms 23892 KB n=500
39 Correct 13 ms 23892 KB n=500
40 Correct 13 ms 23836 KB n=500
41 Correct 13 ms 23852 KB n=500
42 Correct 12 ms 23912 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 12 ms 23892 KB n=500
45 Correct 13 ms 23952 KB n=500
46 Correct 15 ms 23892 KB n=500
47 Correct 13 ms 23892 KB n=500
48 Correct 12 ms 23908 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 12 ms 23892 KB n=500
51 Correct 12 ms 23892 KB n=500
52 Correct 12 ms 23888 KB n=500
53 Correct 13 ms 23836 KB n=500
54 Correct 13 ms 23892 KB n=500
55 Correct 12 ms 23824 KB n=278
56 Correct 13 ms 23892 KB n=500
57 Correct 12 ms 23960 KB n=500
58 Correct 13 ms 23836 KB n=500
59 Correct 16 ms 24276 KB n=2000
60 Correct 15 ms 24404 KB n=2000
61 Correct 15 ms 24324 KB n=2000
62 Correct 15 ms 24276 KB n=2000
63 Correct 18 ms 24276 KB n=2000
64 Correct 15 ms 24312 KB n=2000
65 Correct 15 ms 24316 KB n=2000
66 Correct 14 ms 24280 KB n=2000
67 Correct 15 ms 24276 KB n=2000
68 Correct 15 ms 24276 KB n=2000
69 Correct 14 ms 24276 KB n=2000
70 Correct 15 ms 24312 KB n=2000
71 Correct 18 ms 24276 KB n=2000
72 Correct 15 ms 24184 KB n=2000
73 Correct 14 ms 24264 KB n=2000
74 Correct 15 ms 24284 KB n=1844
75 Correct 14 ms 24216 KB n=2000
76 Correct 14 ms 24276 KB n=2000
77 Correct 18 ms 24308 KB n=2000
78 Correct 18 ms 24276 KB n=2000
79 Correct 14 ms 24276 KB n=2000
80 Correct 14 ms 24276 KB n=2000
81 Correct 14 ms 24356 KB n=2000
82 Correct 15 ms 24268 KB n=2000
83 Correct 19 ms 24404 KB n=2000
84 Correct 16 ms 24268 KB n=2000
85 Correct 16 ms 24276 KB n=2000
86 Correct 15 ms 24348 KB n=2000
87 Correct 15 ms 24216 KB n=2000
88 Correct 15 ms 24344 KB n=2000
89 Correct 15 ms 24308 KB n=2000
90 Correct 15 ms 24352 KB n=2000
91 Correct 16 ms 24268 KB n=2000
92 Correct 610 ms 75376 KB n=200000
93 Correct 647 ms 80240 KB n=200000
94 Correct 508 ms 83616 KB n=200000
95 Correct 603 ms 75076 KB n=200000
96 Correct 587 ms 75164 KB n=200000
97 Correct 734 ms 79280 KB n=200000
98 Correct 611 ms 75204 KB n=200000
99 Correct 769 ms 75452 KB n=200000
100 Correct 614 ms 75260 KB n=200000
101 Correct 498 ms 84844 KB n=200000
102 Correct 389 ms 76344 KB n=200000
103 Correct 368 ms 76264 KB n=200000
104 Correct 374 ms 76372 KB n=200000
105 Correct 385 ms 76764 KB n=200000
106 Correct 376 ms 76748 KB n=200000
107 Correct 395 ms 76824 KB n=200000
108 Correct 647 ms 75340 KB n=200000
109 Correct 638 ms 75212 KB n=200000
110 Correct 630 ms 75372 KB n=200000
111 Correct 637 ms 74540 KB n=200000
112 Correct 505 ms 83800 KB n=200000
113 Correct 675 ms 79260 KB n=200000
114 Correct 674 ms 74668 KB n=200000
115 Correct 818 ms 77260 KB n=200000
116 Correct 583 ms 75456 KB n=200000
117 Correct 505 ms 84300 KB n=200000
118 Correct 786 ms 78156 KB n=200000
119 Correct 582 ms 75336 KB n=200000
120 Correct 439 ms 83836 KB n=200000
121 Correct 439 ms 83836 KB n=200000
122 Correct 423 ms 84008 KB n=200000
123 Correct 391 ms 76564 KB n=200000
124 Incorrect 130 ms 38988 KB Wrong range.
125 Halted 0 ms 0 KB -