| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 861232 | Trisanu_Das | 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>
#define pb push_back
#define ll long long
#define mp make_pair
#define ff first
#define ss second
#define pii pair < int, int >
const int maxn = (int) 1e5 + 10;
using namespace std;
int par[20][200200], lift[200200];
vector<int> adj[200200];
int n, m, q;
void dfs(int u, int p){
par[0][v] = p;
for(int i = 1; i < 19; i++) par[i][u] = par[i - 1][par[i - 1][u]];
lift[u] = lift[p] + 1;
for(auto v : u) if(v != p) dfs(v, u);
}
int a[200200];
set<int> S[200200];
set<int> T[200200];
int lca(int u, int v){
if(lift[u] < lift[v]) swap(u, v);
for(int i = 18; i > -1; i--) if(lift[u] - (1 << i) >= lift[v]) u = par[i][u];
if(u == v) return u;
for(int i = 18; i > -1; i--){
if(par[i][u] != par[i][v]) {
u = par[i][u];
v = par[i][v];
}
}
return par[0][v];
}
int main(){
cin >> n >> m >> q;
for(int i = 1, x, y; i < n; i++){
cin >> x >> y;
adj[x].pb(y);
adj[y].pb(x);
}
for(int i = 1; i < m + 1; i++) cin >> a[i];
dfs(1, 0);
for(int i = 1; i < m + 1; i++) S[a[i]].insert(i);
for(int i = 2; i < m + 1; i++) T[lca(a[i], a[i - 1])].insert(i);
for(int i = 1; i < n + 1; i++) {
S[i].insert(INT_MAX);
T[i].insert(INT_MAX);
}
while(q--){
int op, l, r, v; cin >> op;
if(ty == 1){
cin >> l >> v;
S[a[l]].erase(l);
if(l > 1) T[lca(a[l], a[l - 1])].erase(l);
if(l < m) T[lca(a[l], a[l + 1])].erase(l + 1);
a[l] = v;
S[a[l]].insert(l);
if(l > 1) T[lca(a[l], a[l-1])].insert(l);
if(l < m) T[lca(a[l], a[l+1])].insert(l + 1);
}else{
cin >> l >> r >> v;
int d = *S[v].lower_bound(l), e = *T[v].lower_bound(l+1);
if(d <= r) cout << d << ' ' << d << '\n';
else if(e <= r) cout << e - 1 << ' ' << e << '\n';
else cout << "-1 -1\n";
}
}
}