답안 #97057 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
97057	2019-02-13T14:46:54 Z	Kalam	Birthday gift (IZhO18_treearray)	C++11	56 / 100	2162 ms	82764 KB

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 < 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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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.

답안 #97057

Compilation message

Subtask #1 12.0 / 12.0

Subtask #2 18.0 / 18.0

Subtask #3 26.0 / 26.0

Subtask #4 0 / 44.0

Subtask #1
12.0 / 12.0

Subtask #2
18.0 / 18.0

Subtask #3
26.0 / 26.0

Subtask #4
0 / 44.0