oj.uz

Submission #492350

# Submission time Handle Problem Language Result Execution time Memory
492350 2021-12-07T01:07:24 Z Rainbowbunny Birthday gift (IZhO18_treearray) C++17
100 / 100
 958 ms 84680 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 2e5 + 5;
const int MAXL = 20;

int n, m, q;
int up[MAXN][MAXL], a[MAXN], H[MAXN];
vector <int> Adj[MAXN];

set <int> Pos[MAXN];
set <int> Nex[MAXN];

void DFS(int node, int p = 1)
{
    up[node][0] = p;
    for(int i = 1; i < MAXL; i++)
    {
        up[node][i] = up[up[node][i - 1]][i - 1];
    }
    for(auto x : Adj[node])
    {
        if(x == p)
        {
            continue;
        }
        H[x] = H[node] + 1;
        DFS(x, node);
    }
}

int LCA(int u, int v)
{
    if(H[u] < H[v])
    {
        swap(u, v);
    }
    int tmp = H[u] - H[v];
    for(int i = MAXL - 1; i >= 0; i--)
    {
        if(tmp & (1 << i))
        {
            u = up[u][i];
        }
    }
    if(u == v)
    {
        return u;
    }
    for(int i = MAXL - 1; i >= 0; i--)
    {
        if(up[u][i] != up[v][i])
        {
            u = up[u][i];
            v = up[v][i];
        }
    }
    return up[u][0];
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m >> q;
    for(int i = 1; i < n; i++)
    {
        int u, v;
        cin >> u >> v;
        Adj[u].push_back(v);
        Adj[v].push_back(u);
    }
    DFS(1);
    for(int i = 1; i <= m; i++)
    {
        cin >> a[i];
        Pos[a[i]].insert(i);
        if(i != 1)
        {
            Nex[LCA(a[i - 1], a[i])].insert(i - 1);
        }
    }
    while(q--)
    {
        int Type;
        cin >> Type;
        if(Type == 1)
        {
            int pos, v;
            cin >> pos >> v;
            Pos[a[pos]].erase(pos);
            Pos[v].insert(pos);
            if(pos > 1)
            {
                Nex[LCA(a[pos - 1], a[pos])].erase(pos - 1);
                Nex[LCA(a[pos - 1], v)].insert(pos - 1);
            }
            if(pos < m)
            {
                Nex[LCA(a[pos], a[pos + 1])].erase(pos);
                Nex[LCA(a[pos + 1], v)].insert(pos);
            }
            a[pos] = v;
        }
        else
        {
            int l, r, v;
            cin >> l >> r >> v;
            set <int> :: iterator it;
            it = Pos[v].lower_bound(l);
            if(it != Pos[v].end() and *it <= r)
            {
                cout << *it << ' ' << *it << '\n';
                continue;
            }
            it = Nex[v].lower_bound(l);
            if(it != Nex[v].end() and *it < r)
            {
                cout << *it << ' ' << *it + 1 << '\n';
                continue;
            }
            cout << -1 << ' ' << -1 << '\n';
        }
    }
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23804 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 12 ms 23756 KB n=100
5 Correct 11 ms 23752 KB n=100
6 Correct 11 ms 23816 KB n=100
7 Correct 11 ms 23788 KB n=100
8 Correct 11 ms 23808 KB n=100
9 Correct 14 ms 24012 KB n=100
10 Correct 11 ms 23804 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23840 KB n=100
13 Correct 12 ms 23728 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 11 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23756 KB n=100
18 Correct 13 ms 23812 KB n=100
19 Correct 11 ms 23808 KB n=100
20 Correct 11 ms 23828 KB n=100
21 Correct 11 ms 23812 KB n=100
22 Correct 11 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 12 ms 23812 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23756 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23804 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 12 ms 23756 KB n=100
5 Correct 11 ms 23752 KB n=100
6 Correct 11 ms 23816 KB n=100
7 Correct 11 ms 23788 KB n=100
8 Correct 11 ms 23808 KB n=100
9 Correct 14 ms 24012 KB n=100
10 Correct 11 ms 23804 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23840 KB n=100
13 Correct 12 ms 23728 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 11 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23756 KB n=100
18 Correct 13 ms 23812 KB n=100
19 Correct 11 ms 23808 KB n=100
20 Correct 11 ms 23828 KB n=100
21 Correct 11 ms 23812 KB n=100
22 Correct 11 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 12 ms 23812 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23756 KB n=100
28 Correct 13 ms 23944 KB n=500
29 Correct 11 ms 23884 KB n=500
30 Correct 12 ms 23884 KB n=500
31 Correct 13 ms 23952 KB n=500
32 Correct 12 ms 23884 KB n=500
33 Correct 13 ms 23944 KB n=500
34 Correct 13 ms 24008 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 12 ms 23884 KB n=500
37 Correct 13 ms 23848 KB n=500
38 Correct 12 ms 23884 KB n=500
39 Correct 12 ms 23884 KB n=500
40 Correct 12 ms 23884 KB n=500
41 Correct 12 ms 23948 KB n=500
42 Correct 12 ms 23912 KB n=500
43 Correct 12 ms 23884 KB n=500
44 Correct 13 ms 23916 KB n=500
45 Correct 12 ms 23940 KB n=500
46 Correct 12 ms 23884 KB n=500
47 Correct 13 ms 24012 KB n=500
48 Correct 12 ms 23884 KB n=500
49 Correct 12 ms 23884 KB n=500
50 Correct 12 ms 23944 KB n=500
51 Correct 12 ms 23884 KB n=500
52 Correct 13 ms 23944 KB n=500
53 Correct 13 ms 23864 KB n=500
54 Correct 12 ms 23884 KB n=500
55 Correct 12 ms 23884 KB n=278
56 Correct 12 ms 23916 KB n=500
57 Correct 12 ms 23940 KB n=500
58 Correct 12 ms 23944 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23804 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 12 ms 23756 KB n=100
5 Correct 11 ms 23752 KB n=100
6 Correct 11 ms 23816 KB n=100
7 Correct 11 ms 23788 KB n=100
8 Correct 11 ms 23808 KB n=100
9 Correct 14 ms 24012 KB n=100
10 Correct 11 ms 23804 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23840 KB n=100
13 Correct 12 ms 23728 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 11 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23756 KB n=100
18 Correct 13 ms 23812 KB n=100
19 Correct 11 ms 23808 KB n=100
20 Correct 11 ms 23828 KB n=100
21 Correct 11 ms 23812 KB n=100
22 Correct 11 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 12 ms 23812 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23756 KB n=100
28 Correct 13 ms 23944 KB n=500
29 Correct 11 ms 23884 KB n=500
30 Correct 12 ms 23884 KB n=500
31 Correct 13 ms 23952 KB n=500
32 Correct 12 ms 23884 KB n=500
33 Correct 13 ms 23944 KB n=500
34 Correct 13 ms 24008 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 12 ms 23884 KB n=500
37 Correct 13 ms 23848 KB n=500
38 Correct 12 ms 23884 KB n=500
39 Correct 12 ms 23884 KB n=500
40 Correct 12 ms 23884 KB n=500
41 Correct 12 ms 23948 KB n=500
42 Correct 12 ms 23912 KB n=500
43 Correct 12 ms 23884 KB n=500
44 Correct 13 ms 23916 KB n=500
45 Correct 12 ms 23940 KB n=500
46 Correct 12 ms 23884 KB n=500
47 Correct 13 ms 24012 KB n=500
48 Correct 12 ms 23884 KB n=500
49 Correct 12 ms 23884 KB n=500
50 Correct 12 ms 23944 KB n=500
51 Correct 12 ms 23884 KB n=500
52 Correct 13 ms 23944 KB n=500
53 Correct 13 ms 23864 KB n=500
54 Correct 12 ms 23884 KB n=500
55 Correct 12 ms 23884 KB n=278
56 Correct 12 ms 23916 KB n=500
57 Correct 12 ms 23940 KB n=500
58 Correct 12 ms 23944 KB n=500
59 Correct 13 ms 24200 KB n=2000
60 Correct 15 ms 24396 KB n=2000
61 Correct 15 ms 24376 KB n=2000
62 Correct 15 ms 24332 KB n=2000
63 Correct 15 ms 24268 KB n=2000
64 Correct 14 ms 24268 KB n=2000
65 Correct 14 ms 24300 KB n=2000
66 Correct 15 ms 24368 KB n=2000
67 Correct 15 ms 24268 KB n=2000
68 Correct 15 ms 24268 KB n=2000
69 Correct 16 ms 24268 KB n=2000
70 Correct 14 ms 24264 KB n=2000
71 Correct 14 ms 24264 KB n=2000
72 Correct 13 ms 24268 KB n=2000
73 Correct 13 ms 24200 KB n=2000
74 Correct 14 ms 24276 KB n=1844
75 Correct 14 ms 24200 KB n=2000
76 Correct 15 ms 24268 KB n=2000
77 Correct 14 ms 24268 KB n=2000
78 Correct 14 ms 24268 KB n=2000
79 Correct 14 ms 24268 KB n=2000
80 Correct 14 ms 24396 KB n=2000
81 Correct 15 ms 24240 KB n=2000
82 Correct 14 ms 24268 KB n=2000
83 Correct 14 ms 24284 KB n=2000
84 Correct 15 ms 24308 KB n=2000
85 Correct 14 ms 24248 KB n=2000
86 Correct 15 ms 24308 KB n=2000
87 Correct 15 ms 24312 KB n=2000
88 Correct 15 ms 24460 KB n=2000
89 Correct 15 ms 24368 KB n=2000
90 Correct 15 ms 24396 KB n=2000
91 Correct 18 ms 24268 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 23804 KB n=5
2 Correct 12 ms 23764 KB n=100
3 Correct 11 ms 23756 KB n=100
4 Correct 12 ms 23756 KB n=100
5 Correct 11 ms 23752 KB n=100
6 Correct 11 ms 23816 KB n=100
7 Correct 11 ms 23788 KB n=100
8 Correct 11 ms 23808 KB n=100
9 Correct 14 ms 24012 KB n=100
10 Correct 11 ms 23804 KB n=100
11 Correct 11 ms 23808 KB n=100
12 Correct 11 ms 23840 KB n=100
13 Correct 12 ms 23728 KB n=100
14 Correct 11 ms 23764 KB n=100
15 Correct 11 ms 23756 KB n=100
16 Correct 11 ms 23756 KB n=100
17 Correct 11 ms 23756 KB n=100
18 Correct 13 ms 23812 KB n=100
19 Correct 11 ms 23808 KB n=100
20 Correct 11 ms 23828 KB n=100
21 Correct 11 ms 23812 KB n=100
22 Correct 11 ms 23756 KB n=100
23 Correct 11 ms 23756 KB n=100
24 Correct 12 ms 23812 KB n=100
25 Correct 11 ms 23756 KB n=100
26 Correct 12 ms 23756 KB n=12
27 Correct 12 ms 23756 KB n=100
28 Correct 13 ms 23944 KB n=500
29 Correct 11 ms 23884 KB n=500
30 Correct 12 ms 23884 KB n=500
31 Correct 13 ms 23952 KB n=500
32 Correct 12 ms 23884 KB n=500
33 Correct 13 ms 23944 KB n=500
34 Correct 13 ms 24008 KB n=500
35 Correct 12 ms 23884 KB n=500
36 Correct 12 ms 23884 KB n=500
37 Correct 13 ms 23848 KB n=500
38 Correct 12 ms 23884 KB n=500
39 Correct 12 ms 23884 KB n=500
40 Correct 12 ms 23884 KB n=500
41 Correct 12 ms 23948 KB n=500
42 Correct 12 ms 23912 KB n=500
43 Correct 12 ms 23884 KB n=500
44 Correct 13 ms 23916 KB n=500
45 Correct 12 ms 23940 KB n=500
46 Correct 12 ms 23884 KB n=500
47 Correct 13 ms 24012 KB n=500
48 Correct 12 ms 23884 KB n=500
49 Correct 12 ms 23884 KB n=500
50 Correct 12 ms 23944 KB n=500
51 Correct 12 ms 23884 KB n=500
52 Correct 13 ms 23944 KB n=500
53 Correct 13 ms 23864 KB n=500
54 Correct 12 ms 23884 KB n=500
55 Correct 12 ms 23884 KB n=278
56 Correct 12 ms 23916 KB n=500
57 Correct 12 ms 23940 KB n=500
58 Correct 12 ms 23944 KB n=500
59 Correct 13 ms 24200 KB n=2000
60 Correct 15 ms 24396 KB n=2000
61 Correct 15 ms 24376 KB n=2000
62 Correct 15 ms 24332 KB n=2000
63 Correct 15 ms 24268 KB n=2000
64 Correct 14 ms 24268 KB n=2000
65 Correct 14 ms 24300 KB n=2000
66 Correct 15 ms 24368 KB n=2000
67 Correct 15 ms 24268 KB n=2000
68 Correct 15 ms 24268 KB n=2000
69 Correct 16 ms 24268 KB n=2000
70 Correct 14 ms 24264 KB n=2000
71 Correct 14 ms 24264 KB n=2000
72 Correct 13 ms 24268 KB n=2000
73 Correct 13 ms 24200 KB n=2000
74 Correct 14 ms 24276 KB n=1844
75 Correct 14 ms 24200 KB n=2000
76 Correct 15 ms 24268 KB n=2000
77 Correct 14 ms 24268 KB n=2000
78 Correct 14 ms 24268 KB n=2000
79 Correct 14 ms 24268 KB n=2000
80 Correct 14 ms 24396 KB n=2000
81 Correct 15 ms 24240 KB n=2000
82 Correct 14 ms 24268 KB n=2000
83 Correct 14 ms 24284 KB n=2000
84 Correct 15 ms 24308 KB n=2000
85 Correct 14 ms 24248 KB n=2000
86 Correct 15 ms 24308 KB n=2000
87 Correct 15 ms 24312 KB n=2000
88 Correct 15 ms 24460 KB n=2000
89 Correct 15 ms 24368 KB n=2000
90 Correct 15 ms 24396 KB n=2000
91 Correct 18 ms 24268 KB n=2000
92 Correct 647 ms 73200 KB n=200000
93 Correct 948 ms 78192 KB n=200000
94 Correct 894 ms 82644 KB n=200000
95 Correct 640 ms 72892 KB n=200000
96 Correct 619 ms 72952 KB n=200000
97 Correct 927 ms 76980 KB n=200000
98 Correct 638 ms 73056 KB n=200000
99 Correct 771 ms 72332 KB n=200000
100 Correct 693 ms 73012 KB n=200000
101 Correct 898 ms 84444 KB n=200000
102 Correct 410 ms 73864 KB n=200000
103 Correct 388 ms 73796 KB n=200000
104 Correct 388 ms 73828 KB n=200000
105 Correct 393 ms 73532 KB n=200000
106 Correct 387 ms 73540 KB n=200000
107 Correct 402 ms 73588 KB n=200000
108 Correct 730 ms 72460 KB n=200000
109 Correct 740 ms 72644 KB n=200000
110 Correct 739 ms 72616 KB n=200000
111 Correct 651 ms 72840 KB n=200000
112 Correct 892 ms 83136 KB n=200000
113 Correct 947 ms 77012 KB n=200000
114 Correct 652 ms 72880 KB n=200000
115 Correct 958 ms 74436 KB n=200000
116 Correct 604 ms 72584 KB n=200000
117 Correct 869 ms 83648 KB n=200000
118 Correct 942 ms 75588 KB n=200000
119 Correct 628 ms 72640 KB n=200000
120 Correct 842 ms 84236 KB n=200000
121 Correct 887 ms 84284 KB n=200000
122 Correct 883 ms 84680 KB n=200000
123 Correct 435 ms 73404 KB n=200000
124 Correct 199 ms 39028 KB n=25264