Submission #978900

#TimeUsernameProblemLanguageResultExecution timeMemory
978900irmuunBirthday gift (IZhO18_treearray)C++17
100 / 100
994 ms106040 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long #define pb push_back #define ff first #define ss second #define all(s) s.begin(),s.end() #define rall(s) s.rbegin(),s.rend() const int N=2e5+5; int n,m,q,a[N],par[N][20],dep[N]; vector<int>adj[N]; void dfs(int x,int p){ par[x][0]=p; for(int y:adj[x]){ if(y!=p){ dep[y]=dep[x]+1; dfs(y,x); } } } int up(int x,int d){ for(int i=19;i>=0;i--){ if(d&(1<<i)){ x=par[x][i]; } } return x; } int lca(int x,int y){ if(dep[x]<dep[y]) swap(x,y); x=up(x,dep[x]-dep[y]); for(int i=19;i>=0;i--){ if(par[x][i]!=par[y][i]){ x=par[x][i]; y=par[y][i]; } } if(x!=y) x=par[x][0]; return x; } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<n;i++){ int u,v; cin>>u>>v; adj[u].pb(v); adj[v].pb(u); } set<int>s[N],d[N];// one/two for(int i=1;i<=m;i++){ cin>>a[i]; s[a[i]].insert(i); } dep[1]=0; dfs(1,1); for(int j=1;j<20;j++){ for(int i=1;i<=n;i++){ par[i][j]=par[par[i][j-1]][j-1]; } } for(int i=1;i<m;i++){ d[lca(a[i],a[i+1])].insert(i); } for(int i=1;i<=n;i++){ s[i].insert(m+1); d[i].insert(m+1); } while(q--){ int t; cin>>t; if(t==1){ int pos,v; cin>>pos>>v; s[a[pos]].erase(pos); s[v].insert(pos); if(pos>1){ d[lca(a[pos-1],a[pos])].erase(pos-1); d[lca(a[pos-1],v)].insert(pos-1); } if(pos<m){ d[lca(a[pos],a[pos+1])].erase(pos); d[lca(v,a[pos+1])].insert(pos); } a[pos]=v; } else{ int l,r,u; cin>>l>>r>>u; int x=*s[u].lower_bound(l); if(x<=r){ cout<<x<<' '<<x<<"\n"; continue; } x=*d[u].lower_bound(l); if(x<=r-1){ cout<<x<<' '<<x+1<<"\n"; continue; } cout<<"-1 -1\n"; } } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...