oj.uz

Submission #896091

# Submission time Handle Problem Language Result Execution time Memory
896091 2023-12-31T18:02:06 Z borisAngelov Birthday gift (IZhO18_treearray) C++17
100 / 100
 729 ms 84120 KB 
#include <bits/stdc++.h>

using namespace std;

const int maxn = 200005;
const int maxlog = 19;

int n, m, q;

vector<int> tree[maxn];

int jump[maxn][maxlog + 1];
int depth[maxn];

void dfsLCA(int node, int par, int dep)
{
    depth[node] = dep;

    for (int i = 0; i < tree[node].size(); ++i)
    {
        if (tree[node][i] != par)
        {
            dfsLCA(tree[node][i], node, dep + 1);
            jump[tree[node][i]][0] = node;
        }
    }
}

void buildSparse()
{
    jump[1][0] = 1;

    for (int log = 1; log <= maxlog; ++log)
    {
        for (int node = 1; node <= n; ++node)
        {
            jump[node][log] = jump[jump[node][log - 1]][log - 1];
        }
    }
}

int findLCA(int x, int y)
{
    if (depth[x] < depth[y])
    {
        swap(x, y);
    }

    int diff = depth[x] - depth[y];

    for (int i = 0; i <= maxlog; ++i)
    {
        if ((diff & (1 << i)) != 0)
        {
            x = jump[x][i];
            diff -= (1 << i);

            if (diff == 0)
            {
                break;
            }
        }
    }

    if (x == y)
    {
        return x;
    }

    for (int log = maxlog; log >= 0; --log)
    {
        if (jump[x][log] != jump[y][log])
        {
            x = jump[x][log];
            y = jump[y][log];
        }
    }

    return jump[x][0];
}

int sequence[maxn];

set<int> byValue[maxn];
set<int> byLCA[maxn];

void updateQuery(int pos, int newNode)
{
    int curr = sequence[pos];

    byValue[curr].erase(pos);

    if (pos >= 2)
    {
        int prv = sequence[pos - 1];
        //cout << "delete LCA " << findLCA(prv, curr) << " on pos " << pos << endl;
        //cout << "add LCA " << findLCA(prv, newNode) << " on pos " << pos << endl;
        byLCA[findLCA(prv, curr)].erase(pos);
        byLCA[findLCA(prv, newNode)].insert(pos);
    }

    if (pos <= m - 1)
    {
        int nxt = sequence[pos + 1];
        //cout << "delete LCA " << findLCA(curr, nxt) << " on pos " << pos + 1 << endl;
        //cout << "add LCA " << findLCA(newNode, nxt) << " on pos " << pos + 1 << endl;
        byLCA[findLCA(curr, nxt)].erase(pos + 1);
        byLCA[findLCA(newNode, nxt)].insert(pos + 1);
    }

    sequence[pos] = newNode;
    byValue[sequence[pos]].insert(pos);
}

void solveQuery(int from, int to, int nodeLCA)
{
    if (!byValue[nodeLCA].empty())
    {
        auto it = byValue[nodeLCA].lower_bound(from);

        if (it != byValue[nodeLCA].end() && (*it) <= to)
        {
            int idx = (*it);
            cout << idx << ' ' << idx << "\n";
            return;
        }
    }

    if (!byLCA[nodeLCA].empty())
    {
        auto it = byLCA[nodeLCA].lower_bound(from + 1);

        if (it != byLCA[nodeLCA].end() && (*it) <= to)
        {
            int idx = (*it);
            cout << idx - 1 << ' ' << idx << "\n";
            return;
        }
    }

    cout << -1 << ' ' << -1 << "\n";
}

void fastIO()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    fastIO();

    cin >> n >> m >> q;

    for (int i = 1; i <= n - 1; ++i)
    {
        int x, y;
        cin >> x >> y;

        tree[x].push_back(y);
        tree[y].push_back(x);
    }

    dfsLCA(1, -1, 0);
    buildSparse();

    for (int i = 1; i <= m; ++i)
    {
        cin >> sequence[i];
        byValue[sequence[i]].insert(i);
    }

    for (int i = 2; i <= m; ++i)
    {
        //cout << "add " << findLCA(sequence[i - 1], sequence[i]) << " on position " << i << endl;
        byLCA[findLCA(sequence[i - 1], sequence[i])].insert(i);
    }

    while (q--)
    {
        int type;
        cin >> type;

        if (type == 1)
        {
            int pos, val;
            cin >> pos >> val;
            updateQuery(pos, val);
        }
        else
        {
            int l, r, node;
            cin >> l >> r >> node;
            solveQuery(l, r, node);
        }
    }

    return 0;
}

Compilation message

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

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26712 KB n=5
2 Correct 6 ms 26716 KB n=100
3 Correct 6 ms 26796 KB n=100
4 Correct 6 ms 26712 KB n=100
5 Correct 5 ms 26716 KB n=100
6 Correct 5 ms 26716 KB n=100
7 Correct 7 ms 26800 KB n=100
8 Correct 5 ms 26716 KB n=100
9 Correct 6 ms 26712 KB n=100
10 Correct 6 ms 26716 KB n=100
11 Correct 6 ms 26820 KB n=100
12 Correct 6 ms 26716 KB n=100
13 Correct 6 ms 26712 KB n=100
14 Correct 6 ms 26716 KB n=100
15 Correct 6 ms 26716 KB n=100
16 Correct 6 ms 26712 KB n=100
17 Correct 6 ms 26800 KB n=100
18 Correct 6 ms 26716 KB n=100
19 Correct 6 ms 26712 KB n=100
20 Correct 6 ms 26712 KB n=100
21 Correct 6 ms 26716 KB n=100
22 Correct 6 ms 26712 KB n=100
23 Correct 6 ms 26716 KB n=100
24 Correct 6 ms 26760 KB n=100
25 Correct 6 ms 26712 KB n=100
26 Correct 6 ms 26712 KB n=12
27 Correct 5 ms 26716 KB n=100
28 Correct 6 ms 26716 KB n=500
29 Correct 7 ms 26716 KB n=500
30 Correct 6 ms 26760 KB n=500
31 Correct 6 ms 26968 KB n=500
32 Correct 7 ms 26712 KB n=500
33 Correct 6 ms 26712 KB n=500
34 Correct 6 ms 26712 KB n=500
35 Correct 6 ms 26716 KB n=500
36 Correct 6 ms 26808 KB n=500
37 Correct 6 ms 26716 KB n=500
38 Correct 6 ms 26716 KB n=500
39 Correct 6 ms 26716 KB n=500
40 Correct 6 ms 26716 KB n=500
41 Correct 6 ms 26836 KB n=500
42 Correct 6 ms 26716 KB n=500
43 Correct 6 ms 26716 KB n=500
44 Correct 6 ms 26716 KB n=500
45 Correct 6 ms 26716 KB n=500
46 Correct 7 ms 26716 KB n=500
47 Correct 6 ms 26812 KB n=500
48 Correct 6 ms 26716 KB n=500
49 Correct 6 ms 26716 KB n=500
50 Correct 6 ms 26716 KB n=500
51 Correct 7 ms 26716 KB n=500
52 Correct 6 ms 26716 KB n=500
53 Correct 6 ms 26760 KB n=500
54 Correct 6 ms 26716 KB n=500
55 Correct 6 ms 26716 KB n=278
56 Correct 7 ms 26712 KB n=500
57 Correct 6 ms 26716 KB n=500
58 Correct 6 ms 26716 KB n=500
59 Correct 9 ms 26972 KB n=2000
60 Correct 9 ms 26972 KB n=2000
61 Correct 9 ms 26968 KB n=2000
62 Correct 8 ms 26972 KB n=2000
63 Correct 8 ms 26968 KB n=2000
64 Correct 8 ms 26968 KB n=2000
65 Correct 8 ms 26972 KB n=2000
66 Correct 8 ms 26972 KB n=2000
67 Correct 8 ms 26968 KB n=2000
68 Correct 9 ms 27124 KB n=2000
69 Correct 7 ms 26972 KB n=2000
70 Correct 8 ms 26972 KB n=2000
71 Correct 8 ms 26972 KB n=2000
72 Correct 7 ms 26968 KB n=2000
73 Correct 7 ms 26972 KB n=2000
74 Correct 8 ms 26968 KB n=1844
75 Correct 8 ms 26972 KB n=2000
76 Correct 8 ms 26916 KB n=2000
77 Correct 8 ms 26972 KB n=2000
78 Correct 8 ms 26968 KB n=2000
79 Correct 8 ms 26968 KB n=2000
80 Correct 8 ms 26968 KB n=2000
81 Correct 8 ms 26972 KB n=2000
82 Correct 8 ms 27112 KB n=2000
83 Correct 8 ms 26968 KB n=2000
84 Correct 8 ms 27064 KB n=2000
85 Correct 9 ms 26968 KB n=2000
86 Correct 8 ms 26972 KB n=2000
87 Correct 7 ms 26972 KB n=2000
88 Correct 8 ms 26972 KB n=2000
89 Correct 8 ms 26972 KB n=2000
90 Correct 8 ms 26972 KB n=2000
91 Correct 7 ms 26972 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 26712 KB n=5
2 Correct 6 ms 26716 KB n=100
3 Correct 6 ms 26796 KB n=100
4 Correct 6 ms 26712 KB n=100
5 Correct 5 ms 26716 KB n=100
6 Correct 5 ms 26716 KB n=100
7 Correct 7 ms 26800 KB n=100
8 Correct 5 ms 26716 KB n=100
9 Correct 6 ms 26712 KB n=100
10 Correct 6 ms 26716 KB n=100
11 Correct 6 ms 26820 KB n=100
12 Correct 6 ms 26716 KB n=100
13 Correct 6 ms 26712 KB n=100
14 Correct 6 ms 26716 KB n=100
15 Correct 6 ms 26716 KB n=100
16 Correct 6 ms 26712 KB n=100
17 Correct 6 ms 26800 KB n=100
18 Correct 6 ms 26716 KB n=100
19 Correct 6 ms 26712 KB n=100
20 Correct 6 ms 26712 KB n=100
21 Correct 6 ms 26716 KB n=100
22 Correct 6 ms 26712 KB n=100
23 Correct 6 ms 26716 KB n=100
24 Correct 6 ms 26760 KB n=100
25 Correct 6 ms 26712 KB n=100
26 Correct 6 ms 26712 KB n=12
27 Correct 5 ms 26716 KB n=100
28 Correct 6 ms 26716 KB n=500
29 Correct 7 ms 26716 KB n=500
30 Correct 6 ms 26760 KB n=500
31 Correct 6 ms 26968 KB n=500
32 Correct 7 ms 26712 KB n=500
33 Correct 6 ms 26712 KB n=500
34 Correct 6 ms 26712 KB n=500
35 Correct 6 ms 26716 KB n=500
36 Correct 6 ms 26808 KB n=500
37 Correct 6 ms 26716 KB n=500
38 Correct 6 ms 26716 KB n=500
39 Correct 6 ms 26716 KB n=500
40 Correct 6 ms 26716 KB n=500
41 Correct 6 ms 26836 KB n=500
42 Correct 6 ms 26716 KB n=500
43 Correct 6 ms 26716 KB n=500
44 Correct 6 ms 26716 KB n=500
45 Correct 6 ms 26716 KB n=500
46 Correct 7 ms 26716 KB n=500
47 Correct 6 ms 26812 KB n=500
48 Correct 6 ms 26716 KB n=500
49 Correct 6 ms 26716 KB n=500
50 Correct 6 ms 26716 KB n=500
51 Correct 7 ms 26716 KB n=500
52 Correct 6 ms 26716 KB n=500
53 Correct 6 ms 26760 KB n=500
54 Correct 6 ms 26716 KB n=500
55 Correct 6 ms 26716 KB n=278
56 Correct 7 ms 26712 KB n=500
57 Correct 6 ms 26716 KB n=500
58 Correct 6 ms 26716 KB n=500
59 Correct 9 ms 26972 KB n=2000
60 Correct 9 ms 26972 KB n=2000
61 Correct 9 ms 26968 KB n=2000
62 Correct 8 ms 26972 KB n=2000
63 Correct 8 ms 26968 KB n=2000
64 Correct 8 ms 26968 KB n=2000
65 Correct 8 ms 26972 KB n=2000
66 Correct 8 ms 26972 KB n=2000
67 Correct 8 ms 26968 KB n=2000
68 Correct 9 ms 27124 KB n=2000
69 Correct 7 ms 26972 KB n=2000
70 Correct 8 ms 26972 KB n=2000
71 Correct 8 ms 26972 KB n=2000
72 Correct 7 ms 26968 KB n=2000
73 Correct 7 ms 26972 KB n=2000
74 Correct 8 ms 26968 KB n=1844
75 Correct 8 ms 26972 KB n=2000
76 Correct 8 ms 26916 KB n=2000
77 Correct 8 ms 26972 KB n=2000
78 Correct 8 ms 26968 KB n=2000
79 Correct 8 ms 26968 KB n=2000
80 Correct 8 ms 26968 KB n=2000
81 Correct 8 ms 26972 KB n=2000
82 Correct 8 ms 27112 KB n=2000
83 Correct 8 ms 26968 KB n=2000
84 Correct 8 ms 27064 KB n=2000
85 Correct 9 ms 26968 KB n=2000
86 Correct 8 ms 26972 KB n=2000
87 Correct 7 ms 26972 KB n=2000
88 Correct 8 ms 26972 KB n=2000
89 Correct 8 ms 26972 KB n=2000
90 Correct 8 ms 26972 KB n=2000
91 Correct 7 ms 26972 KB n=2000
92 Correct 467 ms 74672 KB n=200000
93 Correct 662 ms 79416 KB n=200000
94 Correct 729 ms 82768 KB n=200000
95 Correct 439 ms 74468 KB n=200000
96 Correct 475 ms 74668 KB n=200000
97 Correct 708 ms 78720 KB n=200000
98 Correct 467 ms 74528 KB n=200000
99 Correct 529 ms 74676 KB n=200000
100 Correct 462 ms 74580 KB n=200000
101 Correct 669 ms 84120 KB n=200000
102 Correct 271 ms 75492 KB n=200000
103 Correct 286 ms 75852 KB n=200000
104 Correct 276 ms 75604 KB n=200000
105 Correct 254 ms 75892 KB n=200000
106 Correct 267 ms 76052 KB n=200000
107 Correct 264 ms 76088 KB n=200000
108 Correct 512 ms 74596 KB n=200000
109 Correct 499 ms 74624 KB n=200000
110 Correct 515 ms 74548 KB n=200000
111 Correct 461 ms 73800 KB n=200000
112 Correct 653 ms 83068 KB n=200000
113 Correct 678 ms 78472 KB n=200000
114 Correct 443 ms 73924 KB n=200000
115 Correct 665 ms 76516 KB n=200000
116 Correct 436 ms 74440 KB n=200000
117 Correct 640 ms 83396 KB n=200000
118 Correct 631 ms 77492 KB n=200000
119 Correct 448 ms 74560 KB n=200000
120 Correct 589 ms 83264 KB n=200000
121 Correct 548 ms 82944 KB n=200000
122 Correct 679 ms 83612 KB n=200000
123 Correct 261 ms 75768 KB n=200000
124 Correct 104 ms 41300 KB n=25264