oj.uz

Submission #274819

# Submission time Handle Problem Language Result Execution time Memory
274819 2020-08-19T16:14:37 Z HynDuf Birthday gift (IZhO18_treearray) C++14
100 / 100
 1467 ms 82680 KB 
#include <bits/stdc++.h>

#define task "T"
#define all(v) (v).begin(), (v).end()
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rep(i, r, l) for (int i = (r); i >= (l); --i)
#define DB(X) { cerr << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
#define SZ(x) ((int)(x).size())
#define pb push_back
#define eb emplace_back
#define pf push_front
#define F first
#define S second
#define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
#define next ___next
#define prev ___prev
#define y1 ___y1
#define left ___left
#define right ___right
#define y0 ___y0
#define div ___div
#define j0 ___j0
#define jn ___jn

using ll = long long;
using ld = long double;
using ull = unsigned long long;
using namespace std;
typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<ll> vl;
const int N = 2e5 + 2;
int n, m, q, pa[N][18], dep[N], a[N];
vi g[N];
set<int> pos[N], pos1[N];
void dfs(int u, int p)
{
    dep[u] = dep[p] + 1;
    pa[u][0] = p;
    rep(k, 1, 17) pa[u][k] = pa[pa[u][k - 1]][k - 1];
    for (int v : g[u]) if (v != p) dfs(v, u);
}
int lca(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
    Rep(k, 17, 0) if (dep[pa[x][k]] >= dep[y]) x = pa[x][k];
    if (x == y) return x;
    Rep(k, 17, 0) if (pa[x][k] != pa[y][k]) x = pa[x][k], y = pa[y][k];
    return pa[x][0];
}
int main()
{
#ifdef HynDuf
    freopen(task".in", "r", stdin);
    //freopen(task".out", "w", stdout);
#else
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
#endif
    cin >> n >> m >> q;
    rep(i, 2, n)
    {
        int u, v;
        cin >> u >> v;
        g[u].eb(v);
        g[v].eb(u);
    }
    dfs(1, 0);
    rep(i, 1, m) cin >> a[i];
    rep(i, 1, m) pos[a[i]].insert(i);
    rep(i, 2, m)
    {
        int z = lca(a[i], a[i - 1]);
        pos1[z].insert(i - 1);
    }
    while (q--)
    {
        int t, l, r, v;
        cin >> t >> l >> r;
        if (t == 1)
        {
            pos[a[l]].erase(l);
            if (l > 1) pos1[lca(a[l], a[l - 1])].erase(l - 1);
            if (l < m) pos1[lca(a[l], a[l + 1])].erase(l);
            a[l] = r;
            pos[r].insert(l);
            if (l > 1) pos1[lca(r, a[l - 1])].insert(l - 1);
            if (l < m) pos1[lca(r, a[l + 1])].insert(l);

        } else
        {
            cin >> v;
            auto it = pos[v].lower_bound(l);
            if (it != pos[v].end() && *it <= r)
            {
                cout << (*it) << ' ' << (*it) << '\n';
                continue;
            }
            it = pos1[v].lower_bound(l);
            if (it != pos1[v].end() && *it < r)
            {
                cout << (*it) << ' ' << (*it + 1) << '\n';
                continue;
            }
            cout << "-1 -1\n";
        }
    }
    return 0;
}

Subtask #1
12.0 / 12.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
26.0 / 26.0

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

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 23808 KB n=5
2 Correct 16 ms 23808 KB n=100
3 Correct 17 ms 23808 KB n=100
4 Correct 16 ms 23808 KB n=100
5 Correct 17 ms 23808 KB n=100
6 Correct 16 ms 23808 KB n=100
7 Correct 17 ms 23808 KB n=100
8 Correct 16 ms 23808 KB n=100
9 Correct 16 ms 23808 KB n=100
10 Correct 19 ms 23808 KB n=100
11 Correct 16 ms 23808 KB n=100
12 Correct 16 ms 23808 KB n=100
13 Correct 16 ms 23808 KB n=100
14 Correct 16 ms 23808 KB n=100
15 Correct 17 ms 23808 KB n=100
16 Correct 16 ms 23808 KB n=100
17 Correct 16 ms 23808 KB n=100
18 Correct 16 ms 23808 KB n=100
19 Correct 16 ms 23808 KB n=100
20 Correct 16 ms 23808 KB n=100
21 Correct 18 ms 23808 KB n=100
22 Correct 16 ms 23884 KB n=100
23 Correct 17 ms 23808 KB n=100
24 Correct 17 ms 23808 KB n=100
25 Correct 20 ms 23808 KB n=100
26 Correct 19 ms 23808 KB n=12
27 Correct 18 ms 23808 KB n=100
28 Correct 17 ms 23936 KB n=500
29 Correct 17 ms 23936 KB n=500
30 Correct 20 ms 23936 KB n=500
31 Correct 20 ms 23936 KB n=500
32 Correct 20 ms 23936 KB n=500
33 Correct 18 ms 23936 KB n=500
34 Correct 18 ms 23936 KB n=500
35 Correct 17 ms 24064 KB n=500
36 Correct 17 ms 23936 KB n=500
37 Correct 18 ms 23936 KB n=500
38 Correct 19 ms 24064 KB n=500
39 Correct 17 ms 23932 KB n=500
40 Correct 17 ms 23936 KB n=500
41 Correct 19 ms 23936 KB n=500
42 Correct 17 ms 23932 KB n=500
43 Correct 18 ms 23936 KB n=500
44 Correct 17 ms 23936 KB n=500
45 Correct 17 ms 23936 KB n=500
46 Correct 18 ms 23936 KB n=500
47 Correct 17 ms 23936 KB n=500
48 Correct 17 ms 23936 KB n=500
49 Correct 18 ms 23936 KB n=500
50 Correct 18 ms 23936 KB n=500
51 Correct 17 ms 23936 KB n=500
52 Correct 17 ms 23936 KB n=500
53 Correct 17 ms 23936 KB n=500
54 Correct 17 ms 23936 KB n=500
55 Correct 16 ms 23936 KB n=278
56 Correct 17 ms 23936 KB n=500
57 Correct 21 ms 23936 KB n=500
58 Correct 17 ms 23936 KB n=500
59 Correct 20 ms 24312 KB n=2000
60 Correct 21 ms 24448 KB n=2000
61 Correct 24 ms 24448 KB n=2000
62 Correct 20 ms 24320 KB n=2000
63 Correct 25 ms 24320 KB n=2000
64 Correct 21 ms 24320 KB n=2000
65 Correct 21 ms 24320 KB n=2000
66 Correct 24 ms 24448 KB n=2000
67 Correct 21 ms 24320 KB n=2000
68 Correct 20 ms 24320 KB n=2000
69 Correct 19 ms 24352 KB n=2000
70 Correct 20 ms 24320 KB n=2000
71 Correct 22 ms 24312 KB n=2000
72 Correct 22 ms 24320 KB n=2000
73 Correct 19 ms 24320 KB n=2000
74 Correct 20 ms 24320 KB n=1844
75 Correct 20 ms 24312 KB n=2000
76 Correct 24 ms 24320 KB n=2000
77 Correct 21 ms 24320 KB n=2000
78 Correct 20 ms 24320 KB n=2000
79 Correct 20 ms 24320 KB n=2000
80 Correct 20 ms 24448 KB n=2000
81 Correct 24 ms 24312 KB n=2000
82 Correct 21 ms 24320 KB n=2000
83 Correct 20 ms 24448 KB n=2000
84 Correct 21 ms 24320 KB n=2000
85 Correct 20 ms 24320 KB n=2000
86 Correct 20 ms 24320 KB n=2000
87 Correct 20 ms 24320 KB n=2000
88 Correct 20 ms 24448 KB n=2000
89 Correct 20 ms 24448 KB n=2000
90 Correct 20 ms 24448 KB n=2000
91 Correct 19 ms 24320 KB n=2000
92 Correct 850 ms 73208 KB n=200000
93 Correct 1298 ms 78072 KB n=200000
94 Correct 1406 ms 81536 KB n=200000
95 Correct 912 ms 72924 KB n=200000
96 Correct 792 ms 72940 KB n=200000
97 Correct 1467 ms 77176 KB n=200000
98 Correct 837 ms 72944 KB n=200000
99 Correct 1129 ms 73084 KB n=200000
100 Correct 843 ms 73120 KB n=200000
101 Correct 1250 ms 82680 KB n=200000
102 Correct 497 ms 74092 KB n=200000
103 Correct 482 ms 74232 KB n=200000
104 Correct 533 ms 74104 KB n=200000
105 Correct 540 ms 74488 KB n=200000
106 Correct 565 ms 74616 KB n=200000
107 Correct 504 ms 74500 KB n=200000
108 Correct 1010 ms 72952 KB n=200000
109 Correct 1002 ms 73160 KB n=200000
110 Correct 1038 ms 73092 KB n=200000
111 Correct 881 ms 72428 KB n=200000
112 Correct 1289 ms 81656 KB n=200000
113 Correct 1316 ms 77032 KB n=200000
114 Correct 835 ms 72380 KB n=200000
115 Correct 1397 ms 74976 KB n=200000
116 Correct 821 ms 73068 KB n=200000
117 Correct 1290 ms 81912 KB n=200000
118 Correct 1424 ms 75896 KB n=200000
119 Correct 780 ms 73068 KB n=200000
120 Correct 1188 ms 81640 KB n=200000
121 Correct 1287 ms 81628 KB n=200000
122 Correct 1208 ms 81748 KB n=200000
123 Correct 509 ms 74408 KB n=200000
124 Correct 273 ms 38520 KB n=25264