oj.uz

Submission #97059

# Submission time Handle Problem Language Result Execution time Memory
97059 2019-02-13T14:53:41 Z Kalam Birthday gift (IZhO18_treearray) C++11
100 / 100
 1990 ms 75128 KB 
// 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

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.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23936 KB n=5
2 Correct 26 ms 23808 KB n=100
3 Correct 28 ms 23804 KB n=100
4 Correct 25 ms 23800 KB n=100
5 Correct 26 ms 23920 KB n=100
6 Correct 24 ms 23808 KB n=100
7 Correct 25 ms 23808 KB n=100
8 Correct 28 ms 23936 KB n=100
9 Correct 25 ms 23808 KB n=100
10 Correct 25 ms 23808 KB n=100
11 Correct 25 ms 23808 KB n=100
12 Correct 26 ms 23800 KB n=100
13 Correct 26 ms 23808 KB n=100
14 Correct 25 ms 23808 KB n=100
15 Correct 26 ms 23928 KB n=100
16 Correct 29 ms 23808 KB n=100
17 Correct 25 ms 23928 KB n=100
18 Correct 27 ms 23808 KB n=100
19 Correct 27 ms 23808 KB n=100
20 Correct 25 ms 23808 KB n=100
21 Correct 28 ms 23808 KB n=100
22 Correct 25 ms 23928 KB n=100
23 Correct 26 ms 23936 KB n=100
24 Correct 25 ms 23808 KB n=100
25 Correct 27 ms 23808 KB n=100
26 Correct 30 ms 23808 KB n=12
27 Correct 27 ms 23936 KB n=100

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23936 KB n=5
2 Correct 26 ms 23808 KB n=100
3 Correct 28 ms 23804 KB n=100
4 Correct 25 ms 23800 KB n=100
5 Correct 26 ms 23920 KB n=100
6 Correct 24 ms 23808 KB n=100
7 Correct 25 ms 23808 KB n=100
8 Correct 28 ms 23936 KB n=100
9 Correct 25 ms 23808 KB n=100
10 Correct 25 ms 23808 KB n=100
11 Correct 25 ms 23808 KB n=100
12 Correct 26 ms 23800 KB n=100
13 Correct 26 ms 23808 KB n=100
14 Correct 25 ms 23808 KB n=100
15 Correct 26 ms 23928 KB n=100
16 Correct 29 ms 23808 KB n=100
17 Correct 25 ms 23928 KB n=100
18 Correct 27 ms 23808 KB n=100
19 Correct 27 ms 23808 KB n=100
20 Correct 25 ms 23808 KB n=100
21 Correct 28 ms 23808 KB n=100
22 Correct 25 ms 23928 KB n=100
23 Correct 26 ms 23936 KB n=100
24 Correct 25 ms 23808 KB n=100
25 Correct 27 ms 23808 KB n=100
26 Correct 30 ms 23808 KB n=12
27 Correct 27 ms 23936 KB n=100
28 Correct 29 ms 23876 KB n=500
29 Correct 28 ms 24064 KB n=500
30 Correct 29 ms 23808 KB n=500
31 Correct 27 ms 23936 KB n=500
32 Correct 28 ms 23972 KB n=500
33 Correct 28 ms 24064 KB n=500
34 Correct 28 ms 23952 KB n=500
35 Correct 25 ms 23928 KB n=500
36 Correct 30 ms 23936 KB n=500
37 Correct 27 ms 23936 KB n=500
38 Correct 29 ms 23928 KB n=500
39 Correct 25 ms 23928 KB n=500
40 Correct 29 ms 23936 KB n=500
41 Correct 27 ms 23936 KB n=500
42 Correct 26 ms 23936 KB n=500
43 Correct 26 ms 23936 KB n=500
44 Correct 28 ms 24056 KB n=500
45 Correct 29 ms 23928 KB n=500
46 Correct 29 ms 23928 KB n=500
47 Correct 27 ms 23936 KB n=500
48 Correct 29 ms 23936 KB n=500
49 Correct 28 ms 23936 KB n=500
50 Correct 33 ms 23928 KB n=500
51 Correct 34 ms 23928 KB n=500
52 Correct 29 ms 23928 KB n=500
53 Correct 25 ms 23936 KB n=500
54 Correct 28 ms 24056 KB n=500
55 Correct 30 ms 23928 KB n=278
56 Correct 26 ms 23952 KB n=500
57 Correct 27 ms 23928 KB n=500
58 Correct 29 ms 23928 KB n=500

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23936 KB n=5
2 Correct 26 ms 23808 KB n=100
3 Correct 28 ms 23804 KB n=100
4 Correct 25 ms 23800 KB n=100
5 Correct 26 ms 23920 KB n=100
6 Correct 24 ms 23808 KB n=100
7 Correct 25 ms 23808 KB n=100
8 Correct 28 ms 23936 KB n=100
9 Correct 25 ms 23808 KB n=100
10 Correct 25 ms 23808 KB n=100
11 Correct 25 ms 23808 KB n=100
12 Correct 26 ms 23800 KB n=100
13 Correct 26 ms 23808 KB n=100
14 Correct 25 ms 23808 KB n=100
15 Correct 26 ms 23928 KB n=100
16 Correct 29 ms 23808 KB n=100
17 Correct 25 ms 23928 KB n=100
18 Correct 27 ms 23808 KB n=100
19 Correct 27 ms 23808 KB n=100
20 Correct 25 ms 23808 KB n=100
21 Correct 28 ms 23808 KB n=100
22 Correct 25 ms 23928 KB n=100
23 Correct 26 ms 23936 KB n=100
24 Correct 25 ms 23808 KB n=100
25 Correct 27 ms 23808 KB n=100
26 Correct 30 ms 23808 KB n=12
27 Correct 27 ms 23936 KB n=100
28 Correct 29 ms 23876 KB n=500
29 Correct 28 ms 24064 KB n=500
30 Correct 29 ms 23808 KB n=500
31 Correct 27 ms 23936 KB n=500
32 Correct 28 ms 23972 KB n=500
33 Correct 28 ms 24064 KB n=500
34 Correct 28 ms 23952 KB n=500
35 Correct 25 ms 23928 KB n=500
36 Correct 30 ms 23936 KB n=500
37 Correct 27 ms 23936 KB n=500
38 Correct 29 ms 23928 KB n=500
39 Correct 25 ms 23928 KB n=500
40 Correct 29 ms 23936 KB n=500
41 Correct 27 ms 23936 KB n=500
42 Correct 26 ms 23936 KB n=500
43 Correct 26 ms 23936 KB n=500
44 Correct 28 ms 24056 KB n=500
45 Correct 29 ms 23928 KB n=500
46 Correct 29 ms 23928 KB n=500
47 Correct 27 ms 23936 KB n=500
48 Correct 29 ms 23936 KB n=500
49 Correct 28 ms 23936 KB n=500
50 Correct 33 ms 23928 KB n=500
51 Correct 34 ms 23928 KB n=500
52 Correct 29 ms 23928 KB n=500
53 Correct 25 ms 23936 KB n=500
54 Correct 28 ms 24056 KB n=500
55 Correct 30 ms 23928 KB n=278
56 Correct 26 ms 23952 KB n=500
57 Correct 27 ms 23928 KB n=500
58 Correct 29 ms 23928 KB n=500
59 Correct 30 ms 24292 KB n=2000
60 Correct 33 ms 24324 KB n=2000
61 Correct 31 ms 24320 KB n=2000
62 Correct 36 ms 24320 KB n=2000
63 Correct 32 ms 24320 KB n=2000
64 Correct 33 ms 24316 KB n=2000
65 Correct 33 ms 24312 KB n=2000
66 Correct 33 ms 24312 KB n=2000
67 Correct 34 ms 24216 KB n=2000
68 Correct 34 ms 24320 KB n=2000
69 Correct 32 ms 24308 KB n=2000
70 Correct 37 ms 24320 KB n=2000
71 Correct 37 ms 24284 KB n=2000
72 Correct 30 ms 24388 KB n=2000
73 Correct 31 ms 24328 KB n=2000
74 Correct 33 ms 24312 KB n=1844
75 Correct 28 ms 24312 KB n=2000
76 Correct 32 ms 24320 KB n=2000
77 Correct 29 ms 24320 KB n=2000
78 Correct 34 ms 24320 KB n=2000
79 Correct 30 ms 24312 KB n=2000
80 Correct 32 ms 24440 KB n=2000
81 Correct 32 ms 24320 KB n=2000
82 Correct 32 ms 24320 KB n=2000
83 Correct 28 ms 24320 KB n=2000
84 Correct 29 ms 24440 KB n=2000
85 Correct 32 ms 24320 KB n=2000
86 Correct 30 ms 24320 KB n=2000
87 Correct 28 ms 24320 KB n=2000
88 Correct 30 ms 24320 KB n=2000
89 Correct 33 ms 24312 KB n=2000
90 Correct 33 ms 24440 KB n=2000
91 Correct 32 ms 24312 KB n=2000

Subtask #4
44.0 / 44.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 23936 KB n=5
2 Correct 26 ms 23808 KB n=100
3 Correct 28 ms 23804 KB n=100
4 Correct 25 ms 23800 KB n=100
5 Correct 26 ms 23920 KB n=100
6 Correct 24 ms 23808 KB n=100
7 Correct 25 ms 23808 KB n=100
8 Correct 28 ms 23936 KB n=100
9 Correct 25 ms 23808 KB n=100
10 Correct 25 ms 23808 KB n=100
11 Correct 25 ms 23808 KB n=100
12 Correct 26 ms 23800 KB n=100
13 Correct 26 ms 23808 KB n=100
14 Correct 25 ms 23808 KB n=100
15 Correct 26 ms 23928 KB n=100
16 Correct 29 ms 23808 KB n=100
17 Correct 25 ms 23928 KB n=100
18 Correct 27 ms 23808 KB n=100
19 Correct 27 ms 23808 KB n=100
20 Correct 25 ms 23808 KB n=100
21 Correct 28 ms 23808 KB n=100
22 Correct 25 ms 23928 KB n=100
23 Correct 26 ms 23936 KB n=100
24 Correct 25 ms 23808 KB n=100
25 Correct 27 ms 23808 KB n=100
26 Correct 30 ms 23808 KB n=12
27 Correct 27 ms 23936 KB n=100
28 Correct 29 ms 23876 KB n=500
29 Correct 28 ms 24064 KB n=500
30 Correct 29 ms 23808 KB n=500
31 Correct 27 ms 23936 KB n=500
32 Correct 28 ms 23972 KB n=500
33 Correct 28 ms 24064 KB n=500
34 Correct 28 ms 23952 KB n=500
35 Correct 25 ms 23928 KB n=500
36 Correct 30 ms 23936 KB n=500
37 Correct 27 ms 23936 KB n=500
38 Correct 29 ms 23928 KB n=500
39 Correct 25 ms 23928 KB n=500
40 Correct 29 ms 23936 KB n=500
41 Correct 27 ms 23936 KB n=500
42 Correct 26 ms 23936 KB n=500
43 Correct 26 ms 23936 KB n=500
44 Correct 28 ms 24056 KB n=500
45 Correct 29 ms 23928 KB n=500
46 Correct 29 ms 23928 KB n=500
47 Correct 27 ms 23936 KB n=500
48 Correct 29 ms 23936 KB n=500
49 Correct 28 ms 23936 KB n=500
50 Correct 33 ms 23928 KB n=500
51 Correct 34 ms 23928 KB n=500
52 Correct 29 ms 23928 KB n=500
53 Correct 25 ms 23936 KB n=500
54 Correct 28 ms 24056 KB n=500
55 Correct 30 ms 23928 KB n=278
56 Correct 26 ms 23952 KB n=500
57 Correct 27 ms 23928 KB n=500
58 Correct 29 ms 23928 KB n=500
59 Correct 30 ms 24292 KB n=2000
60 Correct 33 ms 24324 KB n=2000
61 Correct 31 ms 24320 KB n=2000
62 Correct 36 ms 24320 KB n=2000
63 Correct 32 ms 24320 KB n=2000
64 Correct 33 ms 24316 KB n=2000
65 Correct 33 ms 24312 KB n=2000
66 Correct 33 ms 24312 KB n=2000
67 Correct 34 ms 24216 KB n=2000
68 Correct 34 ms 24320 KB n=2000
69 Correct 32 ms 24308 KB n=2000
70 Correct 37 ms 24320 KB n=2000
71 Correct 37 ms 24284 KB n=2000
72 Correct 30 ms 24388 KB n=2000
73 Correct 31 ms 24328 KB n=2000
74 Correct 33 ms 24312 KB n=1844
75 Correct 28 ms 24312 KB n=2000
76 Correct 32 ms 24320 KB n=2000
77 Correct 29 ms 24320 KB n=2000
78 Correct 34 ms 24320 KB n=2000
79 Correct 30 ms 24312 KB n=2000
80 Correct 32 ms 24440 KB n=2000
81 Correct 32 ms 24320 KB n=2000
82 Correct 32 ms 24320 KB n=2000
83 Correct 28 ms 24320 KB n=2000
84 Correct 29 ms 24440 KB n=2000
85 Correct 32 ms 24320 KB n=2000
86 Correct 30 ms 24320 KB n=2000
87 Correct 28 ms 24320 KB n=2000
88 Correct 30 ms 24320 KB n=2000
89 Correct 33 ms 24312 KB n=2000
90 Correct 33 ms 24440 KB n=2000
91 Correct 32 ms 24312 KB n=2000
92 Correct 1424 ms 66752 KB n=200000
93 Correct 1965 ms 70520 KB n=200000
94 Correct 1749 ms 73976 KB n=200000
95 Correct 1235 ms 66672 KB n=200000
96 Correct 1366 ms 66844 KB n=200000
97 Correct 1920 ms 69492 KB n=200000
98 Correct 1191 ms 66748 KB n=200000
99 Correct 1450 ms 66132 KB n=200000
100 Correct 1258 ms 66768 KB n=200000
101 Correct 1730 ms 74944 KB n=200000
102 Correct 644 ms 67564 KB n=200000
103 Correct 667 ms 67460 KB n=200000
104 Correct 668 ms 67576 KB n=200000
105 Correct 670 ms 67348 KB n=200000
106 Correct 862 ms 67320 KB n=200000
107 Correct 740 ms 67136 KB n=200000
108 Correct 1394 ms 66224 KB n=200000
109 Correct 1367 ms 66420 KB n=200000
110 Correct 1232 ms 66292 KB n=200000
111 Correct 1220 ms 66656 KB n=200000
112 Correct 1631 ms 74164 KB n=200000
113 Correct 1748 ms 69508 KB n=200000
114 Correct 1228 ms 66576 KB n=200000
115 Correct 1740 ms 67496 KB n=200000
116 Correct 1220 ms 66412 KB n=200000
117 Correct 1757 ms 74412 KB n=200000
118 Correct 1990 ms 68360 KB n=200000
119 Correct 1235 ms 66244 KB n=200000
120 Correct 1671 ms 74616 KB n=200000
121 Correct 1744 ms 74616 KB n=200000
122 Correct 1725 ms 75128 KB n=200000
123 Correct 740 ms 66808 KB n=200000
124 Correct 473 ms 36856 KB n=25264