oj.uz

Submission #97057

# Submission time Handle Problem Language Result Execution time Memory
97057 2019-02-13T14:46:54 Z Kalam Birthday gift (IZhO18_treearray) C++11
56 / 100
 2162 ms 82764 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 < n)
            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 27 ms 23808 KB n=100
4 Correct 29 ms 23800 KB n=100
5 Correct 28 ms 23800 KB n=100
6 Correct 29 ms 23900 KB n=100
7 Correct 30 ms 23936 KB n=100
8 Correct 26 ms 23808 KB n=100
9 Correct 29 ms 23804 KB n=100
10 Correct 26 ms 24064 KB n=100
11 Correct 26 ms 23808 KB n=100
12 Correct 28 ms 23928 KB n=100
13 Correct 27 ms 23808 KB n=100
14 Correct 29 ms 23780 KB n=100
15 Correct 29 ms 23672 KB n=100
16 Correct 29 ms 23800 KB n=100
17 Correct 30 ms 23808 KB n=100
18 Correct 28 ms 23936 KB n=100
19 Correct 28 ms 23800 KB n=100
20 Correct 28 ms 23936 KB n=100
21 Correct 27 ms 23808 KB n=100
22 Correct 29 ms 24004 KB n=100
23 Correct 28 ms 23808 KB n=100
24 Correct 28 ms 23928 KB n=100
25 Correct 28 ms 23808 KB n=100
26 Correct 32 ms 23764 KB n=12
27 Correct 27 ms 23808 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 27 ms 23808 KB n=100
4 Correct 29 ms 23800 KB n=100
5 Correct 28 ms 23800 KB n=100
6 Correct 29 ms 23900 KB n=100
7 Correct 30 ms 23936 KB n=100
8 Correct 26 ms 23808 KB n=100
9 Correct 29 ms 23804 KB n=100
10 Correct 26 ms 24064 KB n=100
11 Correct 26 ms 23808 KB n=100
12 Correct 28 ms 23928 KB n=100
13 Correct 27 ms 23808 KB n=100
14 Correct 29 ms 23780 KB n=100
15 Correct 29 ms 23672 KB n=100
16 Correct 29 ms 23800 KB n=100
17 Correct 30 ms 23808 KB n=100
18 Correct 28 ms 23936 KB n=100
19 Correct 28 ms 23800 KB n=100
20 Correct 28 ms 23936 KB n=100
21 Correct 27 ms 23808 KB n=100
22 Correct 29 ms 24004 KB n=100
23 Correct 28 ms 23808 KB n=100
24 Correct 28 ms 23928 KB n=100
25 Correct 28 ms 23808 KB n=100
26 Correct 32 ms 23764 KB n=12
27 Correct 27 ms 23808 KB n=100
28 Correct 31 ms 23916 KB n=500
29 Correct 26 ms 23936 KB n=500
30 Correct 28 ms 23920 KB n=500
31 Correct 31 ms 23944 KB n=500
32 Correct 31 ms 24064 KB n=500
33 Correct 27 ms 23928 KB n=500
34 Correct 27 ms 23956 KB n=500
35 Correct 34 ms 23904 KB n=500
36 Correct 33 ms 24064 KB n=500
37 Correct 28 ms 23928 KB n=500
38 Correct 30 ms 24064 KB n=500
39 Correct 26 ms 23936 KB n=500
40 Correct 30 ms 23988 KB n=500
41 Correct 35 ms 23928 KB n=500
42 Correct 31 ms 23928 KB n=500
43 Correct 30 ms 23936 KB n=500
44 Correct 34 ms 24052 KB n=500
45 Correct 32 ms 23928 KB n=500
46 Correct 31 ms 23928 KB n=500
47 Correct 28 ms 23936 KB n=500
48 Correct 27 ms 23936 KB n=500
49 Correct 27 ms 23936 KB n=500
50 Correct 28 ms 23936 KB n=500
51 Correct 124 ms 23936 KB n=500
52 Correct 29 ms 23928 KB n=500
53 Correct 31 ms 23936 KB n=500
54 Correct 27 ms 23936 KB n=500
55 Correct 29 ms 23928 KB n=278
56 Correct 29 ms 23928 KB n=500
57 Correct 30 ms 23928 KB n=500
58 Correct 31 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 27 ms 23808 KB n=100
4 Correct 29 ms 23800 KB n=100
5 Correct 28 ms 23800 KB n=100
6 Correct 29 ms 23900 KB n=100
7 Correct 30 ms 23936 KB n=100
8 Correct 26 ms 23808 KB n=100
9 Correct 29 ms 23804 KB n=100
10 Correct 26 ms 24064 KB n=100
11 Correct 26 ms 23808 KB n=100
12 Correct 28 ms 23928 KB n=100
13 Correct 27 ms 23808 KB n=100
14 Correct 29 ms 23780 KB n=100
15 Correct 29 ms 23672 KB n=100
16 Correct 29 ms 23800 KB n=100
17 Correct 30 ms 23808 KB n=100
18 Correct 28 ms 23936 KB n=100
19 Correct 28 ms 23800 KB n=100
20 Correct 28 ms 23936 KB n=100
21 Correct 27 ms 23808 KB n=100
22 Correct 29 ms 24004 KB n=100
23 Correct 28 ms 23808 KB n=100
24 Correct 28 ms 23928 KB n=100
25 Correct 28 ms 23808 KB n=100
26 Correct 32 ms 23764 KB n=12
27 Correct 27 ms 23808 KB n=100
28 Correct 31 ms 23916 KB n=500
29 Correct 26 ms 23936 KB n=500
30 Correct 28 ms 23920 KB n=500
31 Correct 31 ms 23944 KB n=500
32 Correct 31 ms 24064 KB n=500
33 Correct 27 ms 23928 KB n=500
34 Correct 27 ms 23956 KB n=500
35 Correct 34 ms 23904 KB n=500
36 Correct 33 ms 24064 KB n=500
37 Correct 28 ms 23928 KB n=500
38 Correct 30 ms 24064 KB n=500
39 Correct 26 ms 23936 KB n=500
40 Correct 30 ms 23988 KB n=500
41 Correct 35 ms 23928 KB n=500
42 Correct 31 ms 23928 KB n=500
43 Correct 30 ms 23936 KB n=500
44 Correct 34 ms 24052 KB n=500
45 Correct 32 ms 23928 KB n=500
46 Correct 31 ms 23928 KB n=500
47 Correct 28 ms 23936 KB n=500
48 Correct 27 ms 23936 KB n=500
49 Correct 27 ms 23936 KB n=500
50 Correct 28 ms 23936 KB n=500
51 Correct 124 ms 23936 KB n=500
52 Correct 29 ms 23928 KB n=500
53 Correct 31 ms 23936 KB n=500
54 Correct 27 ms 23936 KB n=500
55 Correct 29 ms 23928 KB n=278
56 Correct 29 ms 23928 KB n=500
57 Correct 30 ms 23928 KB n=500
58 Correct 31 ms 23928 KB n=500
59 Correct 34 ms 24312 KB n=2000
60 Correct 33 ms 24440 KB n=2000
61 Correct 31 ms 24448 KB n=2000
62 Correct 34 ms 24320 KB n=2000
63 Correct 34 ms 24448 KB n=2000
64 Correct 31 ms 24312 KB n=2000
65 Correct 33 ms 24284 KB n=2000
66 Correct 32 ms 24412 KB n=2000
67 Correct 36 ms 24312 KB n=2000
68 Correct 32 ms 24312 KB n=2000
69 Correct 31 ms 24284 KB n=2000
70 Correct 36 ms 24312 KB n=2000
71 Correct 29 ms 24320 KB n=2000
72 Correct 31 ms 24312 KB n=2000
73 Correct 31 ms 24312 KB n=2000
74 Correct 31 ms 24320 KB n=1844
75 Correct 36 ms 24320 KB n=2000
76 Correct 32 ms 24296 KB n=2000
77 Correct 30 ms 24292 KB n=2000
78 Correct 33 ms 24348 KB n=2000
79 Correct 32 ms 24320 KB n=2000
80 Correct 35 ms 24440 KB n=2000
81 Correct 32 ms 24296 KB n=2000
82 Correct 84 ms 24312 KB n=2000
83 Correct 33 ms 24320 KB n=2000
84 Correct 32 ms 24320 KB n=2000
85 Correct 37 ms 24312 KB n=2000
86 Correct 32 ms 24328 KB n=2000
87 Correct 39 ms 24312 KB n=2000
88 Correct 39 ms 24440 KB n=2000
89 Correct 29 ms 24320 KB n=2000
90 Correct 33 ms 24440 KB n=2000
91 Correct 30 ms 24312 KB n=2000

Subtask #4
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 27 ms 23808 KB n=100
4 Correct 29 ms 23800 KB n=100
5 Correct 28 ms 23800 KB n=100
6 Correct 29 ms 23900 KB n=100
7 Correct 30 ms 23936 KB n=100
8 Correct 26 ms 23808 KB n=100
9 Correct 29 ms 23804 KB n=100
10 Correct 26 ms 24064 KB n=100
11 Correct 26 ms 23808 KB n=100
12 Correct 28 ms 23928 KB n=100
13 Correct 27 ms 23808 KB n=100
14 Correct 29 ms 23780 KB n=100
15 Correct 29 ms 23672 KB n=100
16 Correct 29 ms 23800 KB n=100
17 Correct 30 ms 23808 KB n=100
18 Correct 28 ms 23936 KB n=100
19 Correct 28 ms 23800 KB n=100
20 Correct 28 ms 23936 KB n=100
21 Correct 27 ms 23808 KB n=100
22 Correct 29 ms 24004 KB n=100
23 Correct 28 ms 23808 KB n=100
24 Correct 28 ms 23928 KB n=100
25 Correct 28 ms 23808 KB n=100
26 Correct 32 ms 23764 KB n=12
27 Correct 27 ms 23808 KB n=100
28 Correct 31 ms 23916 KB n=500
29 Correct 26 ms 23936 KB n=500
30 Correct 28 ms 23920 KB n=500
31 Correct 31 ms 23944 KB n=500
32 Correct 31 ms 24064 KB n=500
33 Correct 27 ms 23928 KB n=500
34 Correct 27 ms 23956 KB n=500
35 Correct 34 ms 23904 KB n=500
36 Correct 33 ms 24064 KB n=500
37 Correct 28 ms 23928 KB n=500
38 Correct 30 ms 24064 KB n=500
39 Correct 26 ms 23936 KB n=500
40 Correct 30 ms 23988 KB n=500
41 Correct 35 ms 23928 KB n=500
42 Correct 31 ms 23928 KB n=500
43 Correct 30 ms 23936 KB n=500
44 Correct 34 ms 24052 KB n=500
45 Correct 32 ms 23928 KB n=500
46 Correct 31 ms 23928 KB n=500
47 Correct 28 ms 23936 KB n=500
48 Correct 27 ms 23936 KB n=500
49 Correct 27 ms 23936 KB n=500
50 Correct 28 ms 23936 KB n=500
51 Correct 124 ms 23936 KB n=500
52 Correct 29 ms 23928 KB n=500
53 Correct 31 ms 23936 KB n=500
54 Correct 27 ms 23936 KB n=500
55 Correct 29 ms 23928 KB n=278
56 Correct 29 ms 23928 KB n=500
57 Correct 30 ms 23928 KB n=500
58 Correct 31 ms 23928 KB n=500
59 Correct 34 ms 24312 KB n=2000
60 Correct 33 ms 24440 KB n=2000
61 Correct 31 ms 24448 KB n=2000
62 Correct 34 ms 24320 KB n=2000
63 Correct 34 ms 24448 KB n=2000
64 Correct 31 ms 24312 KB n=2000
65 Correct 33 ms 24284 KB n=2000
66 Correct 32 ms 24412 KB n=2000
67 Correct 36 ms 24312 KB n=2000
68 Correct 32 ms 24312 KB n=2000
69 Correct 31 ms 24284 KB n=2000
70 Correct 36 ms 24312 KB n=2000
71 Correct 29 ms 24320 KB n=2000
72 Correct 31 ms 24312 KB n=2000
73 Correct 31 ms 24312 KB n=2000
74 Correct 31 ms 24320 KB n=1844
75 Correct 36 ms 24320 KB n=2000
76 Correct 32 ms 24296 KB n=2000
77 Correct 30 ms 24292 KB n=2000
78 Correct 33 ms 24348 KB n=2000
79 Correct 32 ms 24320 KB n=2000
80 Correct 35 ms 24440 KB n=2000
81 Correct 32 ms 24296 KB n=2000
82 Correct 84 ms 24312 KB n=2000
83 Correct 33 ms 24320 KB n=2000
84 Correct 32 ms 24320 KB n=2000
85 Correct 37 ms 24312 KB n=2000
86 Correct 32 ms 24328 KB n=2000
87 Correct 39 ms 24312 KB n=2000
88 Correct 39 ms 24440 KB n=2000
89 Correct 29 ms 24320 KB n=2000
90 Correct 33 ms 24440 KB n=2000
91 Correct 30 ms 24312 KB n=2000
92 Correct 1441 ms 73188 KB n=200000
93 Correct 2162 ms 78016 KB n=200000
94 Correct 1885 ms 81420 KB n=200000
95 Correct 1345 ms 73020 KB n=200000
96 Correct 1225 ms 73196 KB n=200000
97 Correct 2112 ms 77308 KB n=200000
98 Correct 1262 ms 73120 KB n=200000
99 Correct 1574 ms 73120 KB n=200000
100 Correct 1307 ms 72992 KB n=200000
101 Correct 1880 ms 82764 KB n=200000
102 Correct 726 ms 74176 KB n=200000
103 Correct 740 ms 74076 KB n=200000
104 Correct 752 ms 73976 KB n=200000
105 Correct 820 ms 74488 KB n=200000
106 Correct 759 ms 74480 KB n=200000
107 Correct 692 ms 74668 KB n=200000
108 Correct 1310 ms 73136 KB n=200000
109 Correct 1338 ms 73080 KB n=200000
110 Correct 1436 ms 73112 KB n=200000
111 Correct 1455 ms 72404 KB n=200000
112 Correct 2040 ms 81744 KB n=200000
113 Correct 1987 ms 77084 KB n=200000
114 Correct 1284 ms 72496 KB n=200000
115 Correct 1977 ms 74980 KB n=200000
116 Correct 1214 ms 73124 KB n=200000
117 Correct 1954 ms 82040 KB n=200000
118 Correct 2019 ms 75948 KB n=200000
119 Correct 1276 ms 73000 KB n=200000
120 Correct 1688 ms 81436 KB n=200000
121 Correct 1730 ms 81520 KB n=200000
122 Correct 1742 ms 81800 KB n=200000
123 Correct 822 ms 74264 KB n=200000
124 Incorrect 438 ms 38688 KB Wrong range.