| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 90867 | adlet | Birthday gift (IZhO18_treearray) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#define file(s) if (fopen(s".in", "r")) freopen(s".in", "r", stdin), freopen(s".out", "w", stdout)
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
const int mod = 1e9 + 7;
const double PI = acos(-1.0);
const int lg;
int n, m, q, timer, t[N * 4], x[N], lvl[N], tin[N], tout[N], used[N], up[N][lg + 5];
vector < int > g[N];
int dfs(int v, int p = 1, int h = 0) {
used[v] = 1;
up[v][0] = p;
tin[v] = ++timer;
lvl[v] = h;
for (int i = 1; i <= lg; ++i) {
up[v][i] = up[up[v][i - 1]][i - 1];
}
for (int to : g[v]) {
if (!used[to]) {
dfs(to, v, h + 1);
}
}
tout[v] = ++timer;
}
int lca(int a, int b) {
if (lvl[a] < lvl[b])
swap(a, b);
if (tin[b] <= tin[a] && tout[b] >= tout[a])
return b;
for (int i = lg; i >= 0; --i) {
if (lvl[up[a][i]] >= lvl[b]) {
a = up[a][i];
}
}
if (a == b)
return a;
for (int i = lg; i >= 0; --i) {
if (up[a][i] != up[b][i]) {
a = up[a][i];
b = up[b][i];
}
}
return up[a][0];
}
inline void build(int v, int tl, int tr) {
if (tl == tr) {
t[v] = x[tl];
return;
}
int tm = tl + tr >> 1;
build(v + v, tl, tm);
build(v + v + 1, tm + 1, tr);
t[v] = lca(t[v + v], t[v + v + 1]);
}
inline void upd(int v, int tl, int tr, int pos, int x) {
if (tl == tr) {
t[v] = x;
return;
}
int tm = tl + tr >> 1;
if (pos <= tm)
upd(v + v, tl, tm, pos, x);
else
upd(v + v + 1, tm + 1, tr, pos, x);
t[v] = lca(t[v + v], t[v + v + 1]);
}
int get(int v, int tl, int tr, int l, int r) {
if (tl > r || tr < l)
return -1;
if (tl >= l && tr <= r)
return t[v];
int tm = tl + tr >> 1;
int lv = get(v + v, tl, tm, l, r);
int rv = get(v + v + 1, tm + 1, tr, l, r);
if (lv == -1)
lv = rv;
else if (rv == -1)
rv = lv;
return lca(lv, rv);
}
int getq(int l, int r) {
return get(1, 1, m, l, r);
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cin >> n >> m >> q;
lg = log2(n) + 1;
for (int i = 1; i < n; ++i) {
int v, u;
cin >> v >> u;
g[v].push_back(u);
g[u].push_back(v);
}
dfs(1);
for (int i = 1; i <= m; ++i) {
cin >> x[i];
}
build(1, 1, m);
while (q--) {
int ll = -1, rr = -1, l, r, type;
cin >> type >> l >> r;
if (type == 1) {
upd(1, 1, m, l, r);
} else {
int v;
cin >> v;
for (int a = l; a <= r; ++a) {
for (int b = a; b <= r; ++b) {
if (getq(a, b) == v) {
ll = a;
rr = b;
break;
}
}
if (max(ll, rr) != -1)
break;
}
cout << ll << " " << rr << "\n";
}
}
}
/*
5 4 4
1 2
3 1
3 4
5 3
4 5 2 3
2 1 3 1
1 3 5
2 3 4 5
2 1 3 1
*/