oj.uz

Submission #680423

# Submission time Handle Problem Language Result Execution time Memory
680423 2023-01-10T19:00:49 Z phoenix Birthday gift (IZhO18_treearray) C++17
56 / 100
 827 ms 77352 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 < 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 23808 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23856 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23764 KB n=100
6 Correct 12 ms 23848 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 11 ms 23856 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 14 ms 23792 KB n=100
11 Correct 14 ms 23768 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23816 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 12 ms 23760 KB n=100
17 Correct 14 ms 23764 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 13 ms 23824 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 14 ms 23856 KB n=100
22 Correct 13 ms 23732 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 11 ms 23856 KB n=100
25 Correct 11 ms 23764 KB n=100
26 Correct 11 ms 23764 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 23808 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23856 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23764 KB n=100
6 Correct 12 ms 23848 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 11 ms 23856 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 14 ms 23792 KB n=100
11 Correct 14 ms 23768 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23816 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 12 ms 23760 KB n=100
17 Correct 14 ms 23764 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 13 ms 23824 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 14 ms 23856 KB n=100
22 Correct 13 ms 23732 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 11 ms 23856 KB n=100
25 Correct 11 ms 23764 KB n=100
26 Correct 11 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 12 ms 23876 KB n=500
29 Correct 12 ms 23888 KB n=500
30 Correct 12 ms 23952 KB n=500
31 Correct 13 ms 23956 KB n=500
32 Correct 12 ms 23892 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 13 ms 23892 KB n=500
35 Correct 12 ms 23964 KB n=500
36 Correct 13 ms 23876 KB n=500
37 Correct 12 ms 23892 KB n=500
38 Correct 14 ms 24020 KB n=500
39 Correct 12 ms 23948 KB n=500
40 Correct 12 ms 23892 KB n=500
41 Correct 13 ms 23936 KB n=500
42 Correct 14 ms 23896 KB n=500
43 Correct 13 ms 23864 KB n=500
44 Correct 12 ms 23868 KB n=500
45 Correct 12 ms 23892 KB n=500
46 Correct 12 ms 23960 KB n=500
47 Correct 14 ms 23960 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 12 ms 23892 KB n=500
51 Correct 14 ms 23892 KB n=500
52 Correct 13 ms 23940 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 14 ms 23904 KB n=500
55 Correct 13 ms 23892 KB n=278
56 Correct 17 ms 23940 KB n=500
57 Correct 13 ms 24056 KB n=500
58 Correct 13 ms 24044 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23808 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23856 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23764 KB n=100
6 Correct 12 ms 23848 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 11 ms 23856 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 14 ms 23792 KB n=100
11 Correct 14 ms 23768 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23816 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 12 ms 23760 KB n=100
17 Correct 14 ms 23764 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 13 ms 23824 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 14 ms 23856 KB n=100
22 Correct 13 ms 23732 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 11 ms 23856 KB n=100
25 Correct 11 ms 23764 KB n=100
26 Correct 11 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 12 ms 23876 KB n=500
29 Correct 12 ms 23888 KB n=500
30 Correct 12 ms 23952 KB n=500
31 Correct 13 ms 23956 KB n=500
32 Correct 12 ms 23892 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 13 ms 23892 KB n=500
35 Correct 12 ms 23964 KB n=500
36 Correct 13 ms 23876 KB n=500
37 Correct 12 ms 23892 KB n=500
38 Correct 14 ms 24020 KB n=500
39 Correct 12 ms 23948 KB n=500
40 Correct 12 ms 23892 KB n=500
41 Correct 13 ms 23936 KB n=500
42 Correct 14 ms 23896 KB n=500
43 Correct 13 ms 23864 KB n=500
44 Correct 12 ms 23868 KB n=500
45 Correct 12 ms 23892 KB n=500
46 Correct 12 ms 23960 KB n=500
47 Correct 14 ms 23960 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 12 ms 23892 KB n=500
51 Correct 14 ms 23892 KB n=500
52 Correct 13 ms 23940 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 14 ms 23904 KB n=500
55 Correct 13 ms 23892 KB n=278
56 Correct 17 ms 23940 KB n=500
57 Correct 13 ms 24056 KB n=500
58 Correct 13 ms 24044 KB n=500
59 Correct 15 ms 24276 KB n=2000
60 Correct 14 ms 24276 KB n=2000
61 Correct 15 ms 24276 KB n=2000
62 Correct 16 ms 24248 KB n=2000
63 Correct 15 ms 24276 KB n=2000
64 Correct 17 ms 24276 KB n=2000
65 Correct 18 ms 24272 KB n=2000
66 Correct 17 ms 24344 KB n=2000
67 Correct 15 ms 24148 KB n=2000
68 Correct 16 ms 24212 KB n=2000
69 Correct 15 ms 24280 KB n=2000
70 Correct 15 ms 24200 KB n=2000
71 Correct 14 ms 24252 KB n=2000
72 Correct 16 ms 24276 KB n=2000
73 Correct 16 ms 24276 KB n=2000
74 Correct 17 ms 24200 KB n=1844
75 Correct 18 ms 24276 KB n=2000
76 Correct 16 ms 24148 KB n=2000
77 Correct 15 ms 24148 KB n=2000
78 Correct 17 ms 24276 KB n=2000
79 Correct 15 ms 24276 KB n=2000
80 Correct 15 ms 24328 KB n=2000
81 Correct 14 ms 24276 KB n=2000
82 Correct 15 ms 24276 KB n=2000
83 Correct 14 ms 24276 KB n=2000
84 Correct 14 ms 24276 KB n=2000
85 Correct 15 ms 24308 KB n=2000
86 Correct 16 ms 24276 KB n=2000
87 Correct 15 ms 24276 KB n=2000
88 Correct 15 ms 24240 KB n=2000
89 Correct 14 ms 24332 KB n=2000
90 Correct 14 ms 24328 KB n=2000
91 Correct 14 ms 24268 KB n=2000

Subtask #4
0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23808 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 12 ms 23856 KB n=100
4 Correct 12 ms 23764 KB n=100
5 Correct 12 ms 23764 KB n=100
6 Correct 12 ms 23848 KB n=100
7 Correct 12 ms 23764 KB n=100
8 Correct 11 ms 23856 KB n=100
9 Correct 12 ms 23764 KB n=100
10 Correct 14 ms 23792 KB n=100
11 Correct 14 ms 23768 KB n=100
12 Correct 11 ms 23764 KB n=100
13 Correct 12 ms 23764 KB n=100
14 Correct 12 ms 23816 KB n=100
15 Correct 12 ms 23764 KB n=100
16 Correct 12 ms 23760 KB n=100
17 Correct 14 ms 23764 KB n=100
18 Correct 12 ms 23764 KB n=100
19 Correct 13 ms 23824 KB n=100
20 Correct 12 ms 23764 KB n=100
21 Correct 14 ms 23856 KB n=100
22 Correct 13 ms 23732 KB n=100
23 Correct 11 ms 23764 KB n=100
24 Correct 11 ms 23856 KB n=100
25 Correct 11 ms 23764 KB n=100
26 Correct 11 ms 23764 KB n=12
27 Correct 13 ms 23764 KB n=100
28 Correct 12 ms 23876 KB n=500
29 Correct 12 ms 23888 KB n=500
30 Correct 12 ms 23952 KB n=500
31 Correct 13 ms 23956 KB n=500
32 Correct 12 ms 23892 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 13 ms 23892 KB n=500
35 Correct 12 ms 23964 KB n=500
36 Correct 13 ms 23876 KB n=500
37 Correct 12 ms 23892 KB n=500
38 Correct 14 ms 24020 KB n=500
39 Correct 12 ms 23948 KB n=500
40 Correct 12 ms 23892 KB n=500
41 Correct 13 ms 23936 KB n=500
42 Correct 14 ms 23896 KB n=500
43 Correct 13 ms 23864 KB n=500
44 Correct 12 ms 23868 KB n=500
45 Correct 12 ms 23892 KB n=500
46 Correct 12 ms 23960 KB n=500
47 Correct 14 ms 23960 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 12 ms 23892 KB n=500
50 Correct 12 ms 23892 KB n=500
51 Correct 14 ms 23892 KB n=500
52 Correct 13 ms 23940 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 14 ms 23904 KB n=500
55 Correct 13 ms 23892 KB n=278
56 Correct 17 ms 23940 KB n=500
57 Correct 13 ms 24056 KB n=500
58 Correct 13 ms 24044 KB n=500
59 Correct 15 ms 24276 KB n=2000
60 Correct 14 ms 24276 KB n=2000
61 Correct 15 ms 24276 KB n=2000
62 Correct 16 ms 24248 KB n=2000
63 Correct 15 ms 24276 KB n=2000
64 Correct 17 ms 24276 KB n=2000
65 Correct 18 ms 24272 KB n=2000
66 Correct 17 ms 24344 KB n=2000
67 Correct 15 ms 24148 KB n=2000
68 Correct 16 ms 24212 KB n=2000
69 Correct 15 ms 24280 KB n=2000
70 Correct 15 ms 24200 KB n=2000
71 Correct 14 ms 24252 KB n=2000
72 Correct 16 ms 24276 KB n=2000
73 Correct 16 ms 24276 KB n=2000
74 Correct 17 ms 24200 KB n=1844
75 Correct 18 ms 24276 KB n=2000
76 Correct 16 ms 24148 KB n=2000
77 Correct 15 ms 24148 KB n=2000
78 Correct 17 ms 24276 KB n=2000
79 Correct 15 ms 24276 KB n=2000
80 Correct 15 ms 24328 KB n=2000
81 Correct 14 ms 24276 KB n=2000
82 Correct 15 ms 24276 KB n=2000
83 Correct 14 ms 24276 KB n=2000
84 Correct 14 ms 24276 KB n=2000
85 Correct 15 ms 24308 KB n=2000
86 Correct 16 ms 24276 KB n=2000
87 Correct 15 ms 24276 KB n=2000
88 Correct 15 ms 24240 KB n=2000
89 Correct 14 ms 24332 KB n=2000
90 Correct 14 ms 24328 KB n=2000
91 Correct 14 ms 24268 KB n=2000
92 Correct 611 ms 68836 KB n=200000
93 Correct 643 ms 72528 KB n=200000
94 Correct 558 ms 75888 KB n=200000
95 Correct 595 ms 68680 KB n=200000
96 Correct 602 ms 68688 KB n=200000
97 Correct 711 ms 71620 KB n=200000
98 Correct 607 ms 69040 KB n=200000
99 Correct 670 ms 68132 KB n=200000
100 Correct 600 ms 68908 KB n=200000
101 Correct 489 ms 77260 KB n=200000
102 Correct 431 ms 69596 KB n=200000
103 Correct 398 ms 69732 KB n=200000
104 Correct 385 ms 69828 KB n=200000
105 Correct 443 ms 69360 KB n=200000
106 Correct 391 ms 69356 KB n=200000
107 Correct 406 ms 69428 KB n=200000
108 Correct 667 ms 68364 KB n=200000
109 Correct 640 ms 68448 KB n=200000
110 Correct 627 ms 68400 KB n=200000
111 Correct 621 ms 68664 KB n=200000
112 Correct 503 ms 76100 KB n=200000
113 Correct 659 ms 71624 KB n=200000
114 Correct 669 ms 68924 KB n=200000
115 Correct 827 ms 69456 KB n=200000
116 Correct 579 ms 68464 KB n=200000
117 Correct 475 ms 76360 KB n=200000
118 Correct 745 ms 70476 KB n=200000
119 Correct 586 ms 68396 KB n=200000
120 Correct 459 ms 76824 KB n=200000
121 Correct 442 ms 76852 KB n=200000
122 Correct 412 ms 77352 KB n=200000
123 Correct 390 ms 69116 KB n=200000
124 Incorrect 137 ms 37108 KB Wrong range.
125 Halted 0 ms 0 KB -