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;
#define F first
#define S second
#define ll long long
#define maksim gay
#define int ll
#define pb push_back
#define sz(s) (int)s.size()
#define pii pair<int,int>
#define all(v) v.begin(),v.end()
#define mem(a,i) memset(a,i,sizeof(a))
#define in insert
#define lb lower_bound
#define ub upper_bound
const int MAX=4e5+10;
const int inf=1e10;
const int N=2e5;
int n,m,q;
int up[MAX][20];
int tin[MAX],tout[MAX],timer;
vector<int> g[MAX];
int a[MAX];
set<int> p[MAX],p1[MAX];
void dfs(int v,int p=1){
tin[v]=++timer;
up[v][0]=p;
for(int i=1;i<20;i++)up[v][i]=up[up[v][i-1]][i-1];
for(auto to:g[v]){
if(to==p)continue;
dfs(to,v);
}
tout[v]=timer;
}
int par(int u,int v){
return tin[u]<=tin[v]&&tout[v]<=tout[u];
}
int lca(int u,int v){
if(par(u,v))return u;
if(par(v,u))return v;
for(int i=19;i>=0;i--){
if(!par(up[u][i],v)){
u=up[u][i];
}
}
return up[u][0];
}
void upd(int pos,int v){
p1[a[pos]].erase(pos);
if(pos-1>=1){
p[lca(a[pos],a[pos-1])].erase(pos-1);
}
if(pos+1<=n){
p[lca(a[pos],a[pos+1])].erase(pos);
}
a[pos]=v;
p1[a[pos]].in(pos);
if(pos-1>=1){
p[lca(a[pos],a[pos-1])].in(pos-1);
}
if(pos+1<=n){
p[lca(a[pos],a[pos+1])].in(pos);
}
}
void solve(){
cin>>n>>m>>q;
for(int i=1;i<n;i++){
int u,v;
cin>>u>>v;
g[u].pb(v);
g[v].pb(u);
}
dfs(1);
for(int i=1;i<=m;i++){
cin>>a[i];
p1[a[i]].in(i);
}
for(int i=2;i<=m;i++){
p[lca(a[i],a[i-1])].in(i-1);
}
while(q--){
int t;
cin>>t;
if(t==1){
int pos,v;
cin>>pos>>v;
upd(pos,v);
}
else{
int l,r,v;
cin>>l>>r>>v;
auto f=p[v].lb(l);
if(f!=p[v].end()&&*f+1<=r){
cout<<*f<<" "<<*f+1<<"\n";
continue;
}
f=p1[v].lb(l);
if(f!=p1[v].end()&&*f<=r){
cout<<*f<<" "<<*f<<"\n";
continue;
}
cout<<-1<<" "<<-1<<"\n";
}
}
}
main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t=1;
// cin>>t;
while(t--){
solve();
}
}
Compilation message (stderr)
treearray.cpp:117:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
117 | main(){
| ^~~~
# | 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... |