Submission #97059

#	Time	Username	Problem	Language	Result	Execution time	Memory
97059		Kalam	Birthday gift (IZhO18_treearray)	C++11	100 / 100	1990 ms	75128 KiB

treearray

// KALAM
# include<bits/stdc++.h>

using namespace std;

const int N = 200000 + 77 , L = 18;
int n , m , q , d[N] , b[N] , Par[N][L];
vector < int > a[N];
set < int > S[N] , T[N];
void dfs(int v = 1 , int prev = - 1){
   for(int i = 1;i < L;++ i)
      Par[v][i] = Par[Par[v][i - 1]][i - 1];
   for(int u : a[v]){
      if(u == prev)
         continue ;
      Par[u][0] = v;
      d[u] = d[v] + 1;
      dfs(u , v);
   }
}
inline int GetPar(int v , int k){
   for(int i = 0;i < L;++ i)
      if(k & (1 << i))
         v = Par[v][i];
   return v;
}
inline int GetLca(int v , int u){
   if(d[v] < d[u])
      swap(v , u);
   v = GetPar(v , d[v] - d[u]);
   if(v == u)
      return v;
   for(int i = L - 1;i >= 0;-- i)
      if(Par[v][i] != Par[u][i])
         v = Par[v][i] , u = Par[u][i];
   return Par[v][0];
}
int main(){
   scanf("%d %d %d" , & n , & m , & q);
   for(int v , u , i = 1;i < n;++ i){
      scanf("%d %d" , & v , & u);
      a[v].push_back(u);
      a[u].push_back(v);
   }
   dfs();
   for(int i = 1;i <= m;++ i){
      scanf("%d" , b + i);
      T[b[i]].insert(i);
      if(i > 1)
         S[GetLca(b[i - 1] , b[i])].insert(i - 1);
   }
   while(q --){
      int tp , l , r , v;
      scanf("%d %d %d" , & tp , & l , & r);
      if(tp == 2){
         int Ax = - 1 , Ay = - 1;
         scanf("%d" , & v);
         auto it = S[v].lower_bound(l);
         if(it != S[v].end() && (* it) < r)
            Ax = * it , Ay = Ax + 1;
         it = T[v].lower_bound(l);
         if(it != T[v].end() && (* it) <= r)
            Ax = Ay = * it;
         printf("%d %d\n" , Ax , Ay);
      } else {
         T[b[l]].erase(l);
         T[r].insert(l);
         if(l > 1)
            S[GetLca(b[l - 1] , b[l])].erase(l - 1) , S[GetLca(b[l - 1] , r)].insert(l - 1);
         if(l < m)
            S[GetLca(b[l] , b[l + 1])].erase(l) , S[GetLca(b[l + 1] , r)].insert(l);
         b[l] = r;
      }
   }
   return 0;
}

Compilation message (stderr)

treearray.cpp: In function 'int main()':
treearray.cpp:39:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d %d %d" , & n , & m , & q);
    ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:41:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d" , & v , & u);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~
treearray.cpp:47:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d" , b + i);
       ~~~~~^~~~~~~~~~~~~~
treearray.cpp:54:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf("%d %d %d" , & tp , & l , & r);
       ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
treearray.cpp:57:15: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
          scanf("%d" , & v);
          ~~~~~^~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 18 / 18
• Subtask 3: 26 / 26
• Subtask 4: 44 / 44