oj.uz

Submission #752327

# Submission time Handle Problem Language Result Execution time Memory
752327 2023-06-02T20:22:45 Z iulia13 Birthday gift (IZhO18_treearray) C++14
100 / 100
 1549 ms 87068 KB 
#include <bits/stdc++.h>

using namespace std;
const int N = 2e5 + 5;
const int LG = 20;
vector <int> g[N];
set <int> L[N];
set <int> V[N];
int dad[N][LG];
int lvl[N], a[N], n;
void dfs(int nod)
{
    for (auto x : g[nod])
    {
        if (x == dad[nod][0])
            continue;
        dad[x][0] = nod;
        lvl[x] = lvl[nod] + 1;
        dfs(x);
    }
}
void lifting()
{
    for (int j = 1; j < LG; j++)
        for (int i = 1; i <= n; i++)
            dad[i][j] = dad[dad[i][j - 1]][j - 1];
}
int lca(int x, int y)
{
    if (lvl[x] < lvl[y])
        swap(x, y);
    int lg = LG - 1;
    while (lvl[x] > lvl[y] && lg != -1)
    {
        if (lvl[dad[x][lg]] >= lvl[y])
            x = dad[x][lg];
        lg--;
    }
    lg = LG - 1;
    while (x != y && lg != -1)
    {
        if (dad[x][lg] != dad[y][lg])
        {
            x = dad[x][lg];
            y = dad[y][lg];
        }
        lg--;
    }
    if (x == y)
        return x;
    return dad[x][0];
}
int main()
{
    int m, q;
    cin >> n >> m >> q;
    for (int i = 1; i < n; i++)
    {
        int x, y;
        cin >> x >> y;
        g[x].push_back(y);
        g[y].push_back(x);
    }
    dfs(1);
    lifting();
    for (int i = 1; i <= m; i++)
    {
        cin >> a[i];
        V[a[i]].insert(i);
        if (1 < i)
            L[lca(a[i], a[i - 1])].insert(i);
    }
    while(q--)
    {
        int tip;
        cin >> tip;
        if (tip == 1)
        {
            int pos, v;
            cin >> pos >> v;
            V[a[pos]].erase(pos);
            V[v].insert(pos);
            if (pos != 1)
            {
                L[lca(a[pos], a[pos - 1])].erase(pos);
                L[lca(v, a[pos - 1])].insert(pos);
            }
            if (pos != m)
            {
                L[lca(a[pos], a[pos + 1])].erase(pos + 1);
                L[lca(v, a[pos + 1])].insert(pos + 1);
            }
            a[pos] = v;
            continue;
        }
        int l, r,val;
        cin >> l >> r >> val;
        auto it = V[val].lower_bound(l);
        if (it != V[val].end())
        {
            int ll = *it;
            if (ll <= r)
            {
                cout << ll << " " << ll << '\n';
                continue;
            }
        }
        it = L[val].lower_bound(l + 1);
        if (it != L[val].end())
        {
            int lll = *it;
            if (lll <= r)
                cout << lll - 1 << " " << lll;
            else
                cout << -1 << " " << -1;
            cout << '\n';
            continue;
        }
        cout << -1 << " " << -1;
            cout << '\n';
    }
    return 0;
}

Subtask #1
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 13 ms 23796 KB n=100
3 Correct 12 ms 23792 KB n=100
4 Correct 13 ms 23752 KB n=100
5 Correct 13 ms 23764 KB n=100
6 Correct 13 ms 23764 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23784 KB n=100
10 Correct 12 ms 23792 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 14 ms 23800 KB n=100
13 Correct 14 ms 23764 KB n=100
14 Correct 15 ms 23788 KB n=100
15 Correct 12 ms 23792 KB n=100
16 Correct 13 ms 23824 KB n=100
17 Correct 12 ms 23784 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 13 ms 23764 KB n=100
21 Correct 13 ms 23796 KB n=100
22 Correct 13 ms 23712 KB n=100
23 Correct 12 ms 23792 KB n=100
24 Correct 15 ms 23748 KB n=100
25 Correct 16 ms 23788 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 12 ms 23788 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 13 ms 23796 KB n=100
3 Correct 12 ms 23792 KB n=100
4 Correct 13 ms 23752 KB n=100
5 Correct 13 ms 23764 KB n=100
6 Correct 13 ms 23764 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23784 KB n=100
10 Correct 12 ms 23792 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 14 ms 23800 KB n=100
13 Correct 14 ms 23764 KB n=100
14 Correct 15 ms 23788 KB n=100
15 Correct 12 ms 23792 KB n=100
16 Correct 13 ms 23824 KB n=100
17 Correct 12 ms 23784 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 13 ms 23764 KB n=100
21 Correct 13 ms 23796 KB n=100
22 Correct 13 ms 23712 KB n=100
23 Correct 12 ms 23792 KB n=100
24 Correct 15 ms 23748 KB n=100
25 Correct 16 ms 23788 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 12 ms 23788 KB n=100
28 Correct 15 ms 23812 KB n=500
29 Correct 14 ms 23932 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 14 ms 23932 KB n=500
32 Correct 17 ms 23828 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 14 ms 23888 KB n=500
35 Correct 14 ms 23892 KB n=500
36 Correct 15 ms 23804 KB n=500
37 Correct 14 ms 23892 KB n=500
38 Correct 14 ms 23796 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 14 ms 23892 KB n=500
42 Correct 13 ms 23796 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 14 ms 23892 KB n=500
45 Correct 14 ms 23888 KB n=500
46 Correct 14 ms 23928 KB n=500
47 Correct 14 ms 23872 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 14 ms 23808 KB n=500
50 Correct 15 ms 23796 KB n=500
51 Correct 13 ms 23868 KB n=500
52 Correct 13 ms 23892 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 13 ms 23896 KB n=500
55 Correct 13 ms 23764 KB n=278
56 Correct 15 ms 23924 KB n=500
57 Correct 14 ms 23892 KB n=500
58 Correct 15 ms 23892 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 13 ms 23796 KB n=100
3 Correct 12 ms 23792 KB n=100
4 Correct 13 ms 23752 KB n=100
5 Correct 13 ms 23764 KB n=100
6 Correct 13 ms 23764 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23784 KB n=100
10 Correct 12 ms 23792 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 14 ms 23800 KB n=100
13 Correct 14 ms 23764 KB n=100
14 Correct 15 ms 23788 KB n=100
15 Correct 12 ms 23792 KB n=100
16 Correct 13 ms 23824 KB n=100
17 Correct 12 ms 23784 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 13 ms 23764 KB n=100
21 Correct 13 ms 23796 KB n=100
22 Correct 13 ms 23712 KB n=100
23 Correct 12 ms 23792 KB n=100
24 Correct 15 ms 23748 KB n=100
25 Correct 16 ms 23788 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 12 ms 23788 KB n=100
28 Correct 15 ms 23812 KB n=500
29 Correct 14 ms 23932 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 14 ms 23932 KB n=500
32 Correct 17 ms 23828 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 14 ms 23888 KB n=500
35 Correct 14 ms 23892 KB n=500
36 Correct 15 ms 23804 KB n=500
37 Correct 14 ms 23892 KB n=500
38 Correct 14 ms 23796 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 14 ms 23892 KB n=500
42 Correct 13 ms 23796 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 14 ms 23892 KB n=500
45 Correct 14 ms 23888 KB n=500
46 Correct 14 ms 23928 KB n=500
47 Correct 14 ms 23872 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 14 ms 23808 KB n=500
50 Correct 15 ms 23796 KB n=500
51 Correct 13 ms 23868 KB n=500
52 Correct 13 ms 23892 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 13 ms 23896 KB n=500
55 Correct 13 ms 23764 KB n=278
56 Correct 15 ms 23924 KB n=500
57 Correct 14 ms 23892 KB n=500
58 Correct 15 ms 23892 KB n=500
59 Correct 19 ms 24404 KB n=2000
60 Correct 19 ms 24404 KB n=2000
61 Correct 19 ms 24276 KB n=2000
62 Correct 19 ms 24180 KB n=2000
63 Correct 20 ms 24276 KB n=2000
64 Correct 19 ms 24276 KB n=2000
65 Correct 18 ms 24188 KB n=2000
66 Correct 20 ms 24276 KB n=2000
67 Correct 20 ms 24276 KB n=2000
68 Correct 19 ms 24332 KB n=2000
69 Correct 19 ms 24272 KB n=2000
70 Correct 19 ms 24216 KB n=2000
71 Correct 18 ms 24192 KB n=2000
72 Correct 19 ms 24276 KB n=2000
73 Correct 20 ms 24280 KB n=2000
74 Correct 20 ms 24148 KB n=1844
75 Correct 20 ms 24188 KB n=2000
76 Correct 20 ms 24276 KB n=2000
77 Correct 19 ms 24276 KB n=2000
78 Correct 18 ms 24276 KB n=2000
79 Correct 20 ms 24184 KB n=2000
80 Correct 21 ms 24316 KB n=2000
81 Correct 22 ms 24424 KB n=2000
82 Correct 18 ms 24140 KB n=2000
83 Correct 19 ms 24312 KB n=2000
84 Correct 18 ms 24188 KB n=2000
85 Correct 19 ms 24320 KB n=2000
86 Correct 20 ms 24276 KB n=2000
87 Correct 23 ms 24240 KB n=2000
88 Correct 19 ms 24316 KB n=2000
89 Correct 21 ms 24304 KB n=2000
90 Correct 19 ms 24276 KB n=2000
91 Correct 20 ms 24280 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 23764 KB n=5
2 Correct 13 ms 23796 KB n=100
3 Correct 12 ms 23792 KB n=100
4 Correct 13 ms 23752 KB n=100
5 Correct 13 ms 23764 KB n=100
6 Correct 13 ms 23764 KB n=100
7 Correct 13 ms 23892 KB n=100
8 Correct 12 ms 23764 KB n=100
9 Correct 12 ms 23784 KB n=100
10 Correct 12 ms 23792 KB n=100
11 Correct 13 ms 23764 KB n=100
12 Correct 14 ms 23800 KB n=100
13 Correct 14 ms 23764 KB n=100
14 Correct 15 ms 23788 KB n=100
15 Correct 12 ms 23792 KB n=100
16 Correct 13 ms 23824 KB n=100
17 Correct 12 ms 23784 KB n=100
18 Correct 12 ms 23788 KB n=100
19 Correct 13 ms 23764 KB n=100
20 Correct 13 ms 23764 KB n=100
21 Correct 13 ms 23796 KB n=100
22 Correct 13 ms 23712 KB n=100
23 Correct 12 ms 23792 KB n=100
24 Correct 15 ms 23748 KB n=100
25 Correct 16 ms 23788 KB n=100
26 Correct 12 ms 23764 KB n=12
27 Correct 12 ms 23788 KB n=100
28 Correct 15 ms 23812 KB n=500
29 Correct 14 ms 23932 KB n=500
30 Correct 14 ms 23892 KB n=500
31 Correct 14 ms 23932 KB n=500
32 Correct 17 ms 23828 KB n=500
33 Correct 13 ms 23892 KB n=500
34 Correct 14 ms 23888 KB n=500
35 Correct 14 ms 23892 KB n=500
36 Correct 15 ms 23804 KB n=500
37 Correct 14 ms 23892 KB n=500
38 Correct 14 ms 23796 KB n=500
39 Correct 14 ms 23892 KB n=500
40 Correct 14 ms 23892 KB n=500
41 Correct 14 ms 23892 KB n=500
42 Correct 13 ms 23796 KB n=500
43 Correct 13 ms 23892 KB n=500
44 Correct 14 ms 23892 KB n=500
45 Correct 14 ms 23888 KB n=500
46 Correct 14 ms 23928 KB n=500
47 Correct 14 ms 23872 KB n=500
48 Correct 13 ms 23892 KB n=500
49 Correct 14 ms 23808 KB n=500
50 Correct 15 ms 23796 KB n=500
51 Correct 13 ms 23868 KB n=500
52 Correct 13 ms 23892 KB n=500
53 Correct 13 ms 23892 KB n=500
54 Correct 13 ms 23896 KB n=500
55 Correct 13 ms 23764 KB n=278
56 Correct 15 ms 23924 KB n=500
57 Correct 14 ms 23892 KB n=500
58 Correct 15 ms 23892 KB n=500
59 Correct 19 ms 24404 KB n=2000
60 Correct 19 ms 24404 KB n=2000
61 Correct 19 ms 24276 KB n=2000
62 Correct 19 ms 24180 KB n=2000
63 Correct 20 ms 24276 KB n=2000
64 Correct 19 ms 24276 KB n=2000
65 Correct 18 ms 24188 KB n=2000
66 Correct 20 ms 24276 KB n=2000
67 Correct 20 ms 24276 KB n=2000
68 Correct 19 ms 24332 KB n=2000
69 Correct 19 ms 24272 KB n=2000
70 Correct 19 ms 24216 KB n=2000
71 Correct 18 ms 24192 KB n=2000
72 Correct 19 ms 24276 KB n=2000
73 Correct 20 ms 24280 KB n=2000
74 Correct 20 ms 24148 KB n=1844
75 Correct 20 ms 24188 KB n=2000
76 Correct 20 ms 24276 KB n=2000
77 Correct 19 ms 24276 KB n=2000
78 Correct 18 ms 24276 KB n=2000
79 Correct 20 ms 24184 KB n=2000
80 Correct 21 ms 24316 KB n=2000
81 Correct 22 ms 24424 KB n=2000
82 Correct 18 ms 24140 KB n=2000
83 Correct 19 ms 24312 KB n=2000
84 Correct 18 ms 24188 KB n=2000
85 Correct 19 ms 24320 KB n=2000
86 Correct 20 ms 24276 KB n=2000
87 Correct 23 ms 24240 KB n=2000
88 Correct 19 ms 24316 KB n=2000
89 Correct 21 ms 24304 KB n=2000
90 Correct 19 ms 24276 KB n=2000
91 Correct 20 ms 24280 KB n=2000
92 Correct 1018 ms 74600 KB n=200000
93 Correct 1414 ms 81020 KB n=200000
94 Correct 1389 ms 85556 KB n=200000
95 Correct 1041 ms 74260 KB n=200000
96 Correct 982 ms 74452 KB n=200000
97 Correct 1549 ms 79760 KB n=200000
98 Correct 978 ms 74464 KB n=200000
99 Correct 1272 ms 74680 KB n=200000
100 Correct 1036 ms 74352 KB n=200000
101 Correct 1380 ms 87068 KB n=200000
102 Correct 913 ms 75504 KB n=200000
103 Correct 889 ms 75612 KB n=200000
104 Correct 872 ms 75560 KB n=200000
105 Correct 886 ms 75876 KB n=200000
106 Correct 913 ms 75972 KB n=200000
107 Correct 980 ms 75888 KB n=200000
108 Correct 1116 ms 74428 KB n=200000
109 Correct 1135 ms 74524 KB n=200000
110 Correct 1112 ms 74436 KB n=200000
111 Correct 959 ms 73912 KB n=200000
112 Correct 1370 ms 85652 KB n=200000
113 Correct 1388 ms 79640 KB n=200000
114 Correct 975 ms 73820 KB n=200000
115 Correct 1536 ms 76952 KB n=200000
116 Correct 972 ms 74500 KB n=200000
117 Correct 1324 ms 86272 KB n=200000
118 Correct 1505 ms 78160 KB n=200000
119 Correct 990 ms 74792 KB n=200000
120 Correct 1324 ms 86132 KB n=200000
121 Correct 1294 ms 86072 KB n=200000
122 Correct 1252 ms 86360 KB n=200000
123 Correct 914 ms 75708 KB n=200000
124 Correct 351 ms 39064 KB n=25264