Submission #379401

#TimeUsernameProblemLanguageResultExecution timeMemory
379401jass921026Birthday gift (IZhO18_treearray)C++14
100 / 100
1080 ms68076 KiB
#include<bits/stdc++.h> using namespace std; #define jizz ios_base::sync_with_stdio(false);cin.tie(NULL); typedef long long ll; typedef pair<int,int> pii; #define F first #define S second #define ALL(x) (x).begin(),(x).end() #define pb push_back #define mkp make_pair const int MAXN=2E5+10; vector<int> G[MAXN]; set<int> st[MAXN]; int n, m, q, arr[2*MAXN], anc[20][MAXN], dep[MAXN]; void dfs(int x, int f){ anc[0][x]=f; dep[x]=dep[f]+1; for(auto i:G[x]){ if(i==f) continue; dfs(i,x); } } int lca(int u, int v){ if(dep[u]<dep[v]) swap(u,v); int b=dep[u]-dep[v]; for(int c=0;b>0;c++){ if(b%2){ u=anc[c][u]; } b/=2; } if(u==v) return u; for(int i=__lg(n)+1;i>=0;i--){ if(anc[i][u]!=anc[i][v]){ u=anc[i][u]; v=anc[i][v]; } } return anc[0][u]; } int main(){ jizz cin>>n>>m>>q; for(int i=0;i<n-1;i++){ int a, b; cin>>a>>b; G[a].pb(b); G[b].pb(a); } dfs(1,0); for(int i=1;(1<<i)<=n;i++){ for(int j=1;j<=n;j++){ anc[i][j]=anc[i-1][anc[i-1][j]]; } } for(int i=0;i<m;i++){ cin>>arr[2*i]; } for(int i=0;i<m-1;i++){ arr[2*i+1]=lca(arr[2*i],arr[2*i+2]); } for(int i=0;i<2*m-1;i++){ st[arr[i]].insert(i); } for(int i=0;i<q;i++){ int type; cin>>type; if(type==1){ int pos, v; cin>>pos>>v; int p=2*(pos-1); st[arr[p]].erase(p); arr[p]=v; st[arr[p]].insert(p); if(p>0){ st[arr[p-1]].erase(p-1); int c=lca(arr[p-2],v); arr[p-1]=c; st[arr[p-1]].insert(p-1); } if(p<2*(m-1)){ st[arr[p+1]].erase(p+1); int c=lca(v,arr[p+2]); arr[p+1]=c; st[arr[p+1]].insert(p+1); } } else if(type==2){ int l, r, v; cin>>l>>r>>v; l=2*(l-1), r=2*(r-1); auto p=st[v].lower_bound(l); if(p==st[v].end()) cout<<"-1 -1\n"; else if((*p)>r) cout<<"-1 -1\n"; else if((*p)%2) cout<<(*p)/2+1<<" "<<(*p)/2+2<<"\n"; else cout<<(*p)/2+1<<" "<<(*p)/2+1<<"\n"; } } return 0; } /* 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...