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;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> ii;
const int MN = 200200;
const int LOG = 18;
vvi g;
int pa[MN][LOG];
int dord;
int en[MN],ex[MN];
void dfs(int u, int p) {
en[u] = dord;dord++;
pa[u][0] = p;
for(int i=0;i<g[u].size();i++) {
int v = g[u][i];
if(v == p) {continue;}
dfs(v,u);
}
ex[u] = dord;dord++;
}
void proc() {
dord = 0;
dfs(0,0);
for(int j=1;j<LOG;j++) {
for(int i=0;i<g.size();i++) {
pa[i][j] = pa[pa[i][j-1]][j-1];
}
}
}
bool anc(int a, int b) {
return en[a] <= en[b] && ex[a] >= ex[b];
}
int lca(int a, int b) {
if(anc(a,b)) {return a;}
if(anc(b,a)) {return b;}
for(int i=LOG-1;i>=0;i--) {
if(!anc(pa[a][i],b)) {a = pa[a][i];}
}
return pa[a][0];
}
vi wa;
set<int> sa[MN],da[MN];
void up(int idx, int u) {
sa[wa[idx]].erase(idx);
if(idx < wa.size()-1) {
int ol = lca(wa[idx],wa[idx+1]);
da[ol].erase(idx);
int nl = lca(u,wa[idx+1]);
da[nl].insert(idx);
}
if(idx > 0) {
int ol = lca(wa[idx-1],wa[idx]);
da[ol].erase(idx-1);
int nl = lca(u,wa[idx-1]);
da[nl].insert(idx-1);
}
wa[idx] = u;
sa[u].insert(idx);
}
int main() {
ios::sync_with_stdio(0);cin.tie(0);
ll n,m,q;
cin >> n >> m >> q;
g.assign(n,vi());
for(int i=1;i<n;i++) {
ll a,b;
cin >> a >> b;
a--;b--;
g[a].push_back(b);
g[b].push_back(a);
}
proc();
for(int i=0;i<m;i++) {
ll t;
cin >> t;
t--;
wa.push_back(t);
sa[t].insert(i);
}
for(int i=0;i<m-1;i++) {
da[(lca(wa[i],wa[i+1]))].insert(i);
}
while(q--) {
ll op;
cin >> op;
if(op == 1) {
ll id, u;
cin >> id >> u;
id--;u--;
up(id,u);
} else {
ll l,r,u;
cin >> l >> r >> u;
l--;r--;u--;
auto sal = (sa[u].lower_bound(l));
auto dal = (da[u].lower_bound(l));
ii ans = {-1,-1};
if(sal != sa[u].end() && *sal <= r) {
ll re = *sal;
ans = {re+1,re+1};
}
if(dal != da[u].end() && *dal <= r-1) {
ll re = *dal;
ans = {re+1,re+2};
}
cout << ans.first << " " << ans.second << '\n';
}
}
}
Compilation message (stderr)
treearray.cpp: In function 'void dfs(int, int)':
treearray.cpp:16:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | for(int i=0;i<g[u].size();i++) {
| ~^~~~~~~~~~~~
treearray.cpp: In function 'void proc()':
treearray.cpp:27:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
27 | for(int i=0;i<g.size();i++) {
| ~^~~~~~~~~
treearray.cpp: In function 'void up(int, int)':
treearray.cpp:47:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
47 | if(idx < wa.size()-1) {
| ~~~~^~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |