Codeforces Round 530 (Div. 1)

Solutions are presented as using the least memory and the fastest execution time. It also takes the top 10 most recent solutions from each language. If you want to limit to a specific index, click the "Solved" button and go to that problem.

ContestId
Name
Phase
Frozen
Duration (Seconds)
Relative Time
Start Time
1098 Codeforces Round 530 (Div. 1) FINISHED False 9000 190819523 Jan. 5, 2019, 4:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 1097 ) C Construct a tree PROGRAMMING binary search constructive algorithms dfs and similar graphs greedy trees 2300

B'Misha walked through the snowy forest and he was so fascinated by the trees to decide to draw his own tree! Misha would like to construct a rooted tree with n vertices, indexed from 1 to n , where the root has index 1. Every other vertex has a parent p_i , and i is called a child of vertex p_i . Vertex u belongs to the subtree of vertex v iff v is reachable from u while iterating over the parents ( u , p_{u} , p_{p_{u}} , ...). Clearly, v belongs to its own subtree, and the number of vertices in the subtree is called the size of the subtree. Misha is only interested in trees where every vertex belongs to the subtree of vertex 1 . Below there is a tree with 6 vertices. The subtree of vertex 2 contains vertices 2 , 3 , 4 , 5 . Hence the size of its subtree is 4 . The branching coefficient of the tree is defined as the maximum number of children in any vertex. For example, for the tree above the branching coefficient equals 2 . Your task is to construct a tree with n vertices such that the sum of the subtree sizes for all vertices equals s , and the branching coefficient is minimum possible. The only input line contains two integers n and s -- the number of vertices in the tree and the desired sum of the subtree sizes ( 2 <= n <= 10^5 ; 1 <= s <= 10^{10} ). If the required tree does not exist, output xc2 xabNo xc2 xbb. Otherwise output xc2 xabYes xc2 xbb on the first line, and in the next one output integers p_2 , p_3 , ..., p_n , where p_i denotes the parent of vertex i . Below one can find one of the possible solutions for the first sample case. The sum of subtree sizes equals 3 + 1 + 1 = 5 , and the branching coefficient equals 2 . Below one can find one of the possible solutions for the third sample case. The sum of subtree sizes equals 6 + 3 + 2 + 1 + 2 + 1 = 15 , and the branching'...

Tutorials

64331

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
48062931 rainboy C Jan. 7, 2019, 4:24 p.m. OK GNU C11 TESTS 98 343 409600 2300
49985664 geeyiiz C Feb. 16, 2019, 10:26 a.m. OK GNU C11 TESTS 98 343 1228800 2300
48049046 luogu_bot5 C Jan. 7, 2019, 7:14 a.m. OK GNU C++11 TESTS 98 31 6758400 2300
48654351 ReaLNero1 C Jan. 21, 2019, 1:29 a.m. OK GNU C++11 TESTS 98 31 6758400 2300
48046378 luhong C Jan. 7, 2019, 3:39 a.m. OK GNU C++11 TESTS 98 46 204800 2300
48019995 zhouyuyang C Jan. 6, 2019, 4:42 a.m. OK GNU C++11 TESTS 98 46 409600 2300
48045397 frodakcin C Jan. 7, 2019, 2:02 a.m. OK GNU C++11 TESTS 98 46 409600 2300
48387212 dy0607 C Jan. 14, 2019, 1:39 p.m. OK GNU C++11 TESTS 98 46 409600 2300
52311953 Gaozijian C April 4, 2019, 3:04 p.m. OK GNU C++11 TESTS 98 46 614400 2300
48025199 oyqy1203 C Jan. 6, 2019, 8:37 a.m. OK GNU C++11 TESTS 98 46 614400 2300
48021717 shanxizeng C Jan. 6, 2019, 6:13 a.m. OK GNU C++11 TESTS 98 46 716800 2300
56073838 ChthollyTree C June 26, 2019, 11:52 a.m. OK GNU C++11 TESTS 98 46 819200 2300
48017871 cyc4188 C Jan. 6, 2019, 1:49 a.m. OK GNU C++14 TESTS 98 31 7168000 2300
49073541 ACRush C Jan. 27, 2019, 11:48 p.m. OK GNU C++14 TESTS 98 46 0 2300
48007116 zbww C Jan. 5, 2019, 6:39 p.m. OK GNU C++14 TESTS 98 46 409600 2300
48004927 Deng1X C Jan. 5, 2019, 6:26 p.m. OK GNU C++14 TESTS 98 46 409600 2300
47999791 Svyat C Jan. 5, 2019, 5:58 p.m. OK GNU C++14 TESTS 98 46 409600 2300
48030199 apiadu C Jan. 6, 2019, 11:54 a.m. OK GNU C++14 TESTS 98 46 409600 2300
48055465 Toxel C Jan. 7, 2019, 12:03 p.m. OK GNU C++14 TESTS 98 46 409600 2300
59086673 HouZAJ C Aug. 19, 2019, 11:17 a.m. OK GNU C++14 TESTS 98 46 819200 2300
56883042 hellomath C July 12, 2019, 11:19 a.m. OK GNU C++14 TESTS 98 46 819200 2300
53876833 nielswiles C May 8, 2019, 12:26 p.m. OK GNU C++14 TESTS 98 46 819200 2300
48009430 Lollipop C Jan. 5, 2019, 6:54 p.m. OK GNU C++17 TESTS 98 46 307200 2300
48031049 teapotd C Jan. 6, 2019, 12:26 p.m. OK GNU C++17 TESTS 98 46 409600 2300
48586586 lys1280023 C Jan. 19, 2019, 8:08 p.m. OK GNU C++17 TESTS 98 46 614400 2300
48007983 alonefight C Jan. 5, 2019, 6:45 p.m. OK GNU C++17 TESTS 98 46 614400 2300
48004087 Vergara C Jan. 5, 2019, 6:22 p.m. OK GNU C++17 TESTS 98 46 819200 2300
54538243 RedStone C May 23, 2019, 9:34 p.m. OK GNU C++17 TESTS 98 46 819200 2300
54504167 RedStone C May 23, 2019, 2:02 a.m. OK GNU C++17 TESTS 98 46 819200 2300
48176801 RDDCCD C Jan. 10, 2019, 10:06 a.m. OK GNU C++17 TESTS 98 46 1024000 2300
48544199 Qing_Yang C Jan. 18, 2019, 6:23 p.m. OK GNU C++17 TESTS 98 46 1024000 2300
48882335 CiriloMorax17 C Jan. 24, 2019, 10:53 a.m. OK GNU C++17 TESTS 98 46 1024000 2300
48062936 Dukkha C Jan. 7, 2019, 4:24 p.m. OK Java 8 TESTS 98 124 0 2300
47994370 mmaxio C Jan. 5, 2019, 5:34 p.m. OK Java 8 TESTS 98 140 0 2300
47989444 Petr C Jan. 5, 2019, 5:16 p.m. OK Java 8 TESTS 98 140 0 2300
48015443 liymbear C Jan. 5, 2019, 10:10 p.m. OK Java 8 TESTS 98 140 15360000 2300
48004273 liymbear C Jan. 5, 2019, 6:23 p.m. OK Java 8 TESTS 98 155 21708800 2300
47999619 uwi C Jan. 5, 2019, 5:57 p.m. OK Java 8 TESTS 98 156 0 2300
48181370 xodiac C Jan. 10, 2019, 12:41 p.m. OK Java 8 TESTS 98 171 5222400 2300
48006609 Lewin C Jan. 5, 2019, 6:36 p.m. OK Java 8 TESTS 98 187 0 2300
48002242 fetetriste C Jan. 5, 2019, 6:11 p.m. OK Java 8 TESTS 98 202 15974400 2300
50085515 JNUzzh C Feb. 18, 2019, 7:12 a.m. OK Java 8 TESTS 98 233 0 2300
48006763 riantkb C Jan. 5, 2019, 6:37 p.m. OK Mono C# TESTS 98 78 12288000 2300
48000538 chokudai C Jan. 5, 2019, 6:02 p.m. OK Mono C# TESTS 98 108 12492800 2300
48003106 LoneFox C Jan. 5, 2019, 6:16 p.m. OK MS C++ TESTS 98 46 4300800 2300
48042900 olpetOdessaONU C Jan. 6, 2019, 9:32 p.m. OK MS C++ TESTS 98 62 8499200 2300
69067702 AleksanderBalobanov C Jan. 18, 2020, 7:28 p.m. OK MS C++ 2017 TESTS 98 62 9216000 2300
52065770 hld67890 C March 31, 2019, 5:18 a.m. OK MS C++ 2017 TESTS 98 78 15564800 2300
60352851 beginner1010 C Sept. 10, 2019, 2:58 p.m. OK PyPy 3 TESTS 98 249 16179200 2300
48033641 tymo C Jan. 6, 2019, 2:03 p.m. OK PyPy 3 TESTS 98 296 10035200 2300
49168063 pedrofreire C Jan. 29, 2019, 5:08 p.m. OK Python 3 TESTS 98 436 5017600 2300
48024830 whatshisbucket C Jan. 6, 2019, 8:23 a.m. OK Python 3 TESTS 98 436 10547200 2300
48014940 Dmitriy.Belichenko C Jan. 5, 2019, 9:41 p.m. OK Python 3 TESTS 98 561 7372800 2300

remove filters

Back to search problems