Submission #554914

#TimeUsernameProblemLanguageResultExecution timeMemory
554914shahriarkhanBirthday gift (IZhO18_treearray)C++14
100 / 100
1030 ms89612 KiB
#include<bits/stdc++.h> using namespace std ; const int MX = 2e5 + 5 , LG = 25 ; int up[MX][LG] , tin[MX] , tout[MX] , timer ; vector<int> adj[MX] ; set<int> S[MX] , V[MX] ; void dfs(int s , int p) { tin[s] = ++timer ; up[s][0] = p ; for(int i = 1 ; i < LG ; ++i) { up[s][i] = up[up[s][i-1]][i-1] ; } for(int t : adj[s]) { if(t==p) continue ; dfs(t,s) ; } tout[s] = ++timer ; } int is_ancestor(int u , int v) { return ((tin[u]<=tin[v]) && (tout[u]>=tout[v])) ; } int find_lca(int u , int v) { if(is_ancestor(u,v)) return u ; if(is_ancestor(v,u)) return v ; for(int i = LG - 1 ; i >= 0 ; --i) { if(!is_ancestor(up[u][i],v)) { u = up[u][i] ; } } return up[u][0] ; } int main() { int n , m , q ; scanf("%d%d%d",&n,&m,&q) ; for(int i = 1 ; i < n ; ++i) { int a , b ; scanf("%d%d",&a,&b) ; adj[a].push_back(b) ; adj[b].push_back(a) ; } int a[m+2] , b[m+2] ; for(int i = 1 ; i <= m ; ++i) { scanf("%d",&a[i]) ; V[a[i]].insert(i) ; } dfs(1,1) ; for(int i = 1 ; i < m ; ++i) { b[i] = find_lca(a[i],a[i+1]) ; S[b[i]].insert(i) ; } while(q--) { int type ; scanf("%d",&type) ; if(type==1) { int pos , v ; scanf("%d%d",&pos,&v) ; V[a[pos]].erase(pos) ; a[pos] = v ; V[a[pos]].insert(pos) ; if(pos!=m) { S[b[pos]].erase(pos) ; b[pos] = find_lca(a[pos],a[pos+1]) ; S[b[pos]].insert(pos) ; } if(pos!=1) { S[b[pos-1]].erase(pos-1) ; b[pos-1] = find_lca(a[pos-1],a[pos]) ; S[b[pos-1]].insert(pos-1) ; } } else { int l , r , v ; scanf("%d%d%d",&l,&r,&v) ; int L = -1 , R = -1 ; if(!S[v].empty()) { auto it = S[v].lower_bound(l) ; if(it!=S[v].end()) { int cr = *it ; if(cr<r) L = cr , R = cr + 1 ; } } if(!V[v].empty()) { auto it = V[v].lower_bound(l) ; if(it!=V[v].end()) { int cr = *it ; if(cr<=r) L = cr , R = cr ; } } printf("%d %d\n",L,R) ; } } return 0 ; }

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:50:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |     scanf("%d%d%d",&n,&m,&q) ;
      |     ~~~~~^~~~~~~~~~~~~~~~~~~
treearray.cpp:54:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         scanf("%d%d",&a,&b) ;
      |         ~~~~~^~~~~~~~~~~~~~
treearray.cpp:61:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   61 |         scanf("%d",&a[i]) ;
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:73:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         scanf("%d",&type) ;
      |         ~~~~~^~~~~~~~~~~~
treearray.cpp:77:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   77 |             scanf("%d%d",&pos,&v) ;
      |             ~~~~~^~~~~~~~~~~~~~~~
treearray.cpp:97:18: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   97 |             scanf("%d%d%d",&l,&r,&v) ;
      |             ~~~~~^~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...