| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 339782 | wind_reaper | 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.
#include <bits/stdc++.h>
using namespace std;
struct LCA{
vector<int> tin, tout;
vector<vector<int>> adj;
vector<vector<int>> up;
int N, l;
int timer = 0;
void init(int n){
l = ceil(log2(n));
up.resize(n, vector<int>(l+1));
tin.resize(n);
adj.resize(n);
tout.resize(n);
N = n;
}
void dfs(int node, int p){
tin[node] = ++timer;
up[node][0] = p;
for(int i = 1; i <= l; i++)
up[node][i] = up[up[node][i-1]][i-1];
for(int v : adj[node])
if(v != p)
dfs(v, node);
tout[node] = ++timer;
}
bool is_ancestor(int u, int v){
return tin[u] <= tin[v] && tout[u] >= tout[v];
}
int lca(int u, int v){
if(is_anc(u, v))
return u;
if(is_anc(v, u))
return v;
for(int i = l; i >= 0; --i)
if(!is_anc(up[u][i], v))
u = up[u][i];
return up[u][0];
}
};
int32_t main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n, m, q;
cin >> n >> m >> q;
LCA L;
L.init(n);
for(int i = 0; i < n - 1; i++){
int u, v;
cin >> u >> v;
--u, --v;
L.adj[u].push_back(v);
L.adj[v].push_back(u);
}
L.dfs(0, 0);
vector<multiset<int>> lcas(n);
vector<int> arr(m);
for(int i = 0; i < m; i++){
cin >> arr[i];
--arr[i];
lcas[arr[i]].insert(i);
}
for(int i = 0; i < m - 1; i++)
lcas[L.lca(arr[i], arr[i+1])].insert(i);
for(int x = 0; x < q; x++){
int t;
cin >> t;
if(t == 1){
int i, v;
cin >> i >> v;
--i, --v;
int r = L.lca(arr[i], arr[i+1]);
if(i < m - 1) lcas[r].erase(lcas[r].find(i));
r = L.lca(arr[i], arr[i-1]);
if(i > 0) lcas[r].erase(lcas[r].find(i-1));
lcas[arr[i]].erase(lcas[arr[i]].find(i));
arr[i] = v;
if(i < m - 1) lcas[L.lca(arr[i+1], arr[i])].insert(i);
if(i > 0) lcas[L.lca(arr[i], arr[i-1])].insert(i-1);
lcas[arr[i]].insert(i);
}
else{
int l, r, v;
cin >> l >> r >> v;
--l, --r, --v;
auto it = lcas[v].lower_bound(l);
int x = -2, y = -2;
// for(int k : lcas[v])
// cout << k << ' ';
// cout << '\n';
if(it != lcas[v].end() && *it <= r){
if(arr[*it] == v)
x = *it, y = *it;
else x = *it, y = *it + 1;
}
cout << x+1 << ' ' << y+1 << '\n';
}
}
return 0;
}