Submission #927577

#TimeUsernameProblemLanguageResultExecution timeMemory
927577shenfe1Birthday gift (IZhO18_treearray)C++17
56 / 100
781 ms124244 KiB
#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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...