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. |
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'... |
64331 |
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 |
Back to search problems