Submission #167641

#TimeUsernameProblemLanguageResultExecution timeMemory
167641HungAnhGoldIBO2020Birthday gift (IZhO18_treearray)C++14
100 / 100
1342 ms73208 KiB
#include<bits/stdc++.h> using namespace std; const int N=2e5+1; const int LOG=18; set<pair<int,int> > lis[N]; vector<int> adj[N]; int level[N],ancestor[LOG][N],ar[N],lef,rig; void dfs(int x,int p){ for(int i=1;i<LOG;i++){ ancestor[i][x]=ancestor[i-1][ancestor[i-1][x]]; } for(auto i:adj[x]){ if(i!=p){ level[i]=level[x]+1; ancestor[0][i]=x; dfs(i,x); } } } int findd(int x,int k){ while(k){ int y=__lg(k); x=ancestor[y][x]; k-=(1<<y); } return x; } int LCA(int x,int y){ if(level[x]>level[y]){ x=findd(x,level[x]-level[y]); } y=findd(y,level[y]-level[x]); if(x==y){ return x; } for(int i=LOG-1;i>-1;i--){ if(ancestor[i][x]!=ancestor[i][y]){ x=ancestor[i][x],y=ancestor[i][y]; } } return ancestor[0][x]; } signed main(){ ios::sync_with_stdio(0); cin.tie(0); int n,i,j,k,l,m,q; cin>>n>>m>>q; for(i=1;i<n;i++){ cin>>j>>k; adj[j].push_back(k); adj[k].push_back(j); } dfs(1,1); for(i=1;i<=m;i++){ cin>>ar[i]; lis[ar[i]].insert({i,i}); if(i>1){ lis[LCA(ar[i-1],ar[i])].insert({i-1,i}); } } for(i=1;i<=q;i++){ cin>>j; if(j==1){ cin>>k>>l; lis[ar[k]].erase({k,k}); if(k>1){ lis[LCA(ar[k-1],ar[k])].erase({k-1,k}); } if(k<m){ lis[LCA(ar[k],ar[k+1])].erase({k,k+1}); } ar[k]=l; lis[ar[k]].insert({k,k}); if(k>1){ lis[LCA(ar[k-1],ar[k])].insert({k-1,k}); } if(k<m){ lis[LCA(ar[k],ar[k+1])].insert({k,k+1}); } } else{ cin>>j>>k>>l; auto ite=lis[l].lower_bound({j,0}); if(ite==lis[l].end()){ lef=rig=-1; } else{ if(ite->second<=k){ lef=ite->first; rig=ite->second; } else{ lef=rig=-1; } } cout<<lef<<' '<<rig<<'\n'; } } } /* 5 4 4 1 2 3 1 3 4 5 3 4 5 2 3 2 1 3 1 1 3 5 2 3 4 5 2 1 3 1 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...