oj.uz

Submission #502652

# Submission time Handle Problem Language Result Execution time Memory
502652 2022-01-06T11:46:18 Z LucaIlie Birthday gift (IZhO18_treearray) C++17
100 / 100
 1681 ms 126500 KB 
#include <iostream>
#include <vector>
#include <set>
 
#define MAX_N 200000
#define MAX_M 200000
#define MAX_LG2N 18
 
using namespace std;
 
struct nodEuler {
    int nod, depth;
 
    bool operator < (const nodEuler &a) const {
        return depth < a.depth;
    }
};
 
struct solutie {
    int lca, left, right;
 
    bool operator < (const solutie &a) const {
        if ( lca == a.lca ) {
            if ( left == a.left )
                return right < a.right;
            return left < a.left;
        }
        return lca < a.lca;
    }
};
 
int eulerSize;
int poz[MAX_N], lg2[2 * MAX_N + 1], v[MAX_M];
nodEuler euler[2 * MAX_N], rmq[2 * MAX_N][MAX_LG2N + 1];
vector <int> muchii[MAX_N];
set <solutie> s;
 
void dfs( int parent, int nod, int depth ) {
    int i;
 
    euler[eulerSize] = { nod, depth };
    poz[nod] = eulerSize;
    eulerSize++;
    for ( i = 0; i < muchii[nod].size(); i++ ) {
        if ( muchii[nod][i] != parent ) {
            dfs( nod, muchii[nod][i], depth + 1 );
            euler[eulerSize] = { nod, depth };
            poz[nod] = eulerSize;
            eulerSize++;
        }
    }
}
 
void initLCA() {
    int i, j;
 
    dfs( -1, 0, 0 );
 
    for ( i = 0; i < eulerSize; i++ )
        rmq[i][0] = euler[i];
    for ( j = 1; (1 << j) <= eulerSize; j++ ) {
        for ( i = 0; i + (1 << j) <= eulerSize; i++ ) {
            if ( rmq[i][j - 1] < rmq[i + (1 << (j - 1))][j - 1] )
                rmq[i][j] = rmq[i][j - 1];
            else
                rmq[i][j] = rmq[i + (1 << (j - 1))][j - 1];
        }
    }
 
    for ( i = 2; i <= eulerSize; i++ )
        lg2[i] = lg2[i / 2] + 1;
}
 
int queryLCA( int x, int y ) {
    int s, d, aux, j;
 
    s = poz[x];
    d = poz[y];
    if ( s > d ) {
        aux = s;
        s = d;
        d = aux;
    }
 
    j = lg2[d - s + 1] ;
    if ( rmq[s][j] < rmq[d - (1 << j) + 1][j] )
        return rmq[s][j].nod;
    return rmq[d - (1 << j) + 1][j].nod;
};
 
int main() {
    int n, m, q, x, y, tip, l, r, p, i;
 
    cin >> n >> m >> q;
    for ( i = 0; i < n - 1; i++ ) {
        cin >> x >> y;
        x--;
        y--;
 
        muchii[x].push_back( y );
        muchii[y].push_back( x );
    }
 
    initLCA();
 
    for ( i = 0; i < m; i++ ) {
        cin >> v[i];
        v[i]--;
 
        s.insert( { v[i], i, i } );
        if( i > 0 )
            s.insert( { queryLCA( v[i - 1], v[i] ), i - 1, i } );
    }
 
    for ( i = 0; i < q; i++ ) {
        cin >> tip;
 
        if ( tip == 1 ) {
            cin >> p >> x;
            p--;
            x--;
 
            s.erase( { v[p], p, p } );
            if ( p > 0 )
                s.erase( { queryLCA( v[p - 1], v[p] ), p - 1, p } );
            if ( p < m - 1 )
                s.erase( { queryLCA( v[p], v[p + 1] ), p, p + 1 } );
 
            v[p] = x;
 
            s.insert( { v[p], p, p } );
            if ( p > 0 )
                s.insert( { queryLCA( v[p - 1], v[p] ), p - 1, p } );
            if ( p < m - 1 )
                s.insert( { queryLCA( v[p], v[p + 1] ), p, p + 1 } );
        } else {
            cin >> l >> r >> x;
            l--;
            r--;
            x--;
 
            auto it = s.lower_bound( { x, l, 0 } );
            if ( it != s.end() && it->lca == x && it->left >= l && it->right <= r )
                cout << it->left + 1 << " " << it->right + 1 << "\n";
            else
                cout << "-1 -1\n";
        }
    }
    return 0;
}

Compilation message

treearray.cpp: In function 'void dfs(int, int, int)':
treearray.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |     for ( i = 0; i < muchii[nod].size(); i++ ) {
      |                  ~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB n=5
2 Correct 3 ms 5068 KB n=100
3 Correct 3 ms 4976 KB n=100
4 Correct 3 ms 4988 KB n=100
5 Correct 3 ms 4988 KB n=100
6 Correct 3 ms 5068 KB n=100
7 Correct 3 ms 5068 KB n=100
8 Correct 4 ms 5004 KB n=100
9 Correct 3 ms 5004 KB n=100
10 Correct 3 ms 4996 KB n=100
11 Correct 3 ms 5068 KB n=100
12 Correct 3 ms 5068 KB n=100
13 Correct 3 ms 5068 KB n=100
14 Correct 3 ms 5068 KB n=100
15 Correct 3 ms 5004 KB n=100
16 Correct 3 ms 5068 KB n=100
17 Correct 3 ms 4996 KB n=100
18 Correct 3 ms 5068 KB n=100
19 Correct 4 ms 4996 KB n=100
20 Correct 4 ms 5068 KB n=100
21 Correct 4 ms 5004 KB n=100
22 Correct 3 ms 5068 KB n=100
23 Correct 3 ms 5068 KB n=100
24 Correct 3 ms 5068 KB n=100
25 Correct 3 ms 5068 KB n=100
26 Correct 4 ms 4940 KB n=12
27 Correct 3 ms 5068 KB n=100
28 Correct 4 ms 5196 KB n=500
29 Correct 4 ms 5196 KB n=500
30 Correct 4 ms 5272 KB n=500
31 Correct 5 ms 5260 KB n=500
32 Correct 4 ms 5196 KB n=500
33 Correct 4 ms 5196 KB n=500
34 Correct 6 ms 5196 KB n=500
35 Correct 4 ms 5196 KB n=500
36 Correct 4 ms 5196 KB n=500
37 Correct 5 ms 5196 KB n=500
38 Correct 4 ms 5196 KB n=500
39 Correct 4 ms 5260 KB n=500
40 Correct 4 ms 5196 KB n=500
41 Correct 4 ms 5196 KB n=500
42 Correct 5 ms 5256 KB n=500
43 Correct 4 ms 5196 KB n=500
44 Correct 4 ms 5196 KB n=500
45 Correct 4 ms 5196 KB n=500
46 Correct 4 ms 5196 KB n=500
47 Correct 4 ms 5196 KB n=500
48 Correct 5 ms 5260 KB n=500
49 Correct 4 ms 5196 KB n=500
50 Correct 4 ms 5196 KB n=500
51 Correct 4 ms 5196 KB n=500
52 Correct 4 ms 5268 KB n=500
53 Correct 4 ms 5196 KB n=500
54 Correct 4 ms 5196 KB n=500
55 Correct 3 ms 5196 KB n=278
56 Correct 4 ms 5196 KB n=500
57 Correct 4 ms 5196 KB n=500
58 Correct 5 ms 5196 KB n=500
59 Correct 9 ms 6036 KB n=2000
60 Correct 10 ms 6092 KB n=2000
61 Correct 9 ms 6092 KB n=2000
62 Correct 9 ms 6000 KB n=2000
63 Correct 10 ms 6092 KB n=2000
64 Correct 10 ms 6092 KB n=2000
65 Correct 9 ms 6036 KB n=2000
66 Correct 9 ms 6164 KB n=2000
67 Correct 9 ms 5964 KB n=2000
68 Correct 9 ms 6024 KB n=2000
69 Correct 14 ms 5964 KB n=2000
70 Correct 11 ms 5964 KB n=2000
71 Correct 12 ms 6064 KB n=2000
72 Correct 13 ms 5964 KB n=2000
73 Correct 10 ms 5964 KB n=2000
74 Correct 9 ms 5964 KB n=1844
75 Correct 10 ms 5964 KB n=2000
76 Correct 9 ms 5964 KB n=2000
77 Correct 9 ms 5964 KB n=2000
78 Correct 9 ms 5964 KB n=2000
79 Correct 9 ms 5964 KB n=2000
80 Correct 10 ms 6092 KB n=2000
81 Correct 9 ms 6092 KB n=2000
82 Correct 8 ms 5964 KB n=2000
83 Correct 10 ms 6036 KB n=2000
84 Correct 10 ms 5964 KB n=2000
85 Correct 10 ms 6040 KB n=2000
86 Correct 10 ms 6040 KB n=2000
87 Correct 9 ms 5964 KB n=2000
88 Correct 12 ms 6092 KB n=2000
89 Correct 9 ms 6128 KB n=2000
90 Correct 9 ms 6128 KB n=2000
91 Correct 10 ms 6064 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB n=5
2 Correct 3 ms 5068 KB n=100
3 Correct 3 ms 4976 KB n=100
4 Correct 3 ms 4988 KB n=100
5 Correct 3 ms 4988 KB n=100
6 Correct 3 ms 5068 KB n=100
7 Correct 3 ms 5068 KB n=100
8 Correct 4 ms 5004 KB n=100
9 Correct 3 ms 5004 KB n=100
10 Correct 3 ms 4996 KB n=100
11 Correct 3 ms 5068 KB n=100
12 Correct 3 ms 5068 KB n=100
13 Correct 3 ms 5068 KB n=100
14 Correct 3 ms 5068 KB n=100
15 Correct 3 ms 5004 KB n=100
16 Correct 3 ms 5068 KB n=100
17 Correct 3 ms 4996 KB n=100
18 Correct 3 ms 5068 KB n=100
19 Correct 4 ms 4996 KB n=100
20 Correct 4 ms 5068 KB n=100
21 Correct 4 ms 5004 KB n=100
22 Correct 3 ms 5068 KB n=100
23 Correct 3 ms 5068 KB n=100
24 Correct 3 ms 5068 KB n=100
25 Correct 3 ms 5068 KB n=100
26 Correct 4 ms 4940 KB n=12
27 Correct 3 ms 5068 KB n=100
28 Correct 4 ms 5196 KB n=500
29 Correct 4 ms 5196 KB n=500
30 Correct 4 ms 5272 KB n=500
31 Correct 5 ms 5260 KB n=500
32 Correct 4 ms 5196 KB n=500
33 Correct 4 ms 5196 KB n=500
34 Correct 6 ms 5196 KB n=500
35 Correct 4 ms 5196 KB n=500
36 Correct 4 ms 5196 KB n=500
37 Correct 5 ms 5196 KB n=500
38 Correct 4 ms 5196 KB n=500
39 Correct 4 ms 5260 KB n=500
40 Correct 4 ms 5196 KB n=500
41 Correct 4 ms 5196 KB n=500
42 Correct 5 ms 5256 KB n=500
43 Correct 4 ms 5196 KB n=500
44 Correct 4 ms 5196 KB n=500
45 Correct 4 ms 5196 KB n=500
46 Correct 4 ms 5196 KB n=500
47 Correct 4 ms 5196 KB n=500
48 Correct 5 ms 5260 KB n=500
49 Correct 4 ms 5196 KB n=500
50 Correct 4 ms 5196 KB n=500
51 Correct 4 ms 5196 KB n=500
52 Correct 4 ms 5268 KB n=500
53 Correct 4 ms 5196 KB n=500
54 Correct 4 ms 5196 KB n=500
55 Correct 3 ms 5196 KB n=278
56 Correct 4 ms 5196 KB n=500
57 Correct 4 ms 5196 KB n=500
58 Correct 5 ms 5196 KB n=500
59 Correct 9 ms 6036 KB n=2000
60 Correct 10 ms 6092 KB n=2000
61 Correct 9 ms 6092 KB n=2000
62 Correct 9 ms 6000 KB n=2000
63 Correct 10 ms 6092 KB n=2000
64 Correct 10 ms 6092 KB n=2000
65 Correct 9 ms 6036 KB n=2000
66 Correct 9 ms 6164 KB n=2000
67 Correct 9 ms 5964 KB n=2000
68 Correct 9 ms 6024 KB n=2000
69 Correct 14 ms 5964 KB n=2000
70 Correct 11 ms 5964 KB n=2000
71 Correct 12 ms 6064 KB n=2000
72 Correct 13 ms 5964 KB n=2000
73 Correct 10 ms 5964 KB n=2000
74 Correct 9 ms 5964 KB n=1844
75 Correct 10 ms 5964 KB n=2000
76 Correct 9 ms 5964 KB n=2000
77 Correct 9 ms 5964 KB n=2000
78 Correct 9 ms 5964 KB n=2000
79 Correct 9 ms 5964 KB n=2000
80 Correct 10 ms 6092 KB n=2000
81 Correct 9 ms 6092 KB n=2000
82 Correct 8 ms 5964 KB n=2000
83 Correct 10 ms 6036 KB n=2000
84 Correct 10 ms 5964 KB n=2000
85 Correct 10 ms 6040 KB n=2000
86 Correct 10 ms 6040 KB n=2000
87 Correct 9 ms 5964 KB n=2000
88 Correct 12 ms 6092 KB n=2000
89 Correct 9 ms 6128 KB n=2000
90 Correct 9 ms 6128 KB n=2000
91 Correct 10 ms 6064 KB n=2000
92 Correct 1450 ms 110456 KB n=200000
93 Correct 1681 ms 118444 KB n=200000
94 Correct 1600 ms 124092 KB n=200000
95 Correct 1518 ms 110212 KB n=200000
96 Correct 1367 ms 110216 KB n=200000
97 Correct 1559 ms 116908 KB n=200000
98 Correct 1345 ms 110220 KB n=200000
99 Correct 1546 ms 110388 KB n=200000
100 Correct 1388 ms 110340 KB n=200000
101 Correct 1527 ms 126500 KB n=200000
102 Correct 1064 ms 111532 KB n=200000
103 Correct 1071 ms 111612 KB n=200000
104 Correct 1012 ms 111564 KB n=200000
105 Correct 1043 ms 111836 KB n=200000
106 Correct 1052 ms 111864 KB n=200000
107 Correct 1053 ms 111880 KB n=200000
108 Correct 1549 ms 110464 KB n=200000
109 Correct 1324 ms 110308 KB n=200000
110 Correct 1330 ms 110604 KB n=200000
111 Correct 1259 ms 109852 KB n=200000
112 Correct 1469 ms 124396 KB n=200000
113 Correct 1384 ms 116904 KB n=200000
114 Correct 1240 ms 109884 KB n=200000
115 Correct 1548 ms 113568 KB n=200000
116 Correct 1345 ms 110524 KB n=200000
117 Correct 1512 ms 125104 KB n=200000
118 Correct 1559 ms 115164 KB n=200000
119 Correct 1285 ms 110564 KB n=200000
120 Correct 1292 ms 125148 KB n=200000
121 Correct 1340 ms 125244 KB n=200000
122 Correct 1299 ms 125564 KB n=200000
123 Correct 1016 ms 111844 KB n=200000
124 Correct 336 ms 29508 KB n=25264