Codeforces Round 431 (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
848 Codeforces Round 431 (Div. 1) FINISHED False 7200 233857493 Sept. 1, 2017, 1:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 390 ) D Shake It! PROGRAMMING combinatorics dp flows graphs 2900

B"A never-ending, fast-changing and dream-like world unfolds, as the secret door opens. A world is an unordered graph G, in whose vertex set V(G) there are two special vertices s(G) and t(G). An initial world has vertex set {s(G), xe2 x80 x89t(G)} and an edge between them. A total of n changes took place in an initial world. In each change, a new vertex w is added into V(G), an existing edge (u, xe2 x80 x89v) is chosen, and two edges (u, xe2 x80 x89w) and (v, xe2 x80 x89w) are added into E(G). Note that it's possible that some edges are chosen in more than one change. It's known that the capacity of the minimum s-t cut of the resulting graph is m, that is, at least m edges need to be removed in order to make s(G) and t(G) disconnected. Count the number of non-similar worlds that can be built under the constraints, modulo 109 xe2 x80 x89+ xe2 x80 x897. We define two worlds similar, if they are isomorphic and there is isomorphism in which the s and t vertices are not relabelled. Formally, two worlds G and H are considered similar, if there is a bijection between their vertex sets , such that: The first and only line of input contains two space-separated integers n, m (1 xe2 x80 x89 xe2 x89 xa4 xe2 x80 x89n, xe2 x80 x89m xe2 x80 x89 xe2 x89 xa4 xe2 x80 x8950) -- the number of operations performed and the minimum cut, respectively. Output one integer -- the number of non-similar worlds that can be built, modulo 109 xe2 x80 x89+ xe2 x80 x897. In the first example, the following 6 worlds are pairwise non-similar and satisfy the constraints, with s(G) marked in green, t(G) marked in blue, and one of their minimum cuts in light blue. In the second example, the following 3 worlds satisfy the constraints. "...

Tutorials

Codeforces Round #431 Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
30034770 laofudasuan D Sept. 3, 2017, 12:54 p.m. OK GNU C++ TESTS 50 31 102400 2900
30030817 gjghfd D Sept. 3, 2017, 11:05 a.m. OK GNU C++ TESTS 50 46 0 2900
30088127 MemS D Sept. 5, 2017, 1:49 a.m. OK GNU C++ TESTS 50 46 204800 2900
34039900 Worldwide_D D Jan. 9, 2018, 4:01 a.m. OK GNU C++ TESTS 50 46 1945600 2900
36294912 Heaplax D March 15, 2018, 9:51 a.m. OK GNU C++ TESTS 50 46 2150400 2900
36244376 QQ_kotori D March 13, 2018, 10:13 a.m. OK GNU C++ TESTS 50 46 2150400 2900
30798861 vjudge1 D Sept. 28, 2017, 8:30 a.m. OK GNU C++ TESTS 50 93 0 2900
30798609 Magolor D Sept. 28, 2017, 8:18 a.m. OK GNU C++ TESTS 50 93 0 2900
30323383 samjia2000 D Sept. 14, 2017, 8:57 a.m. OK GNU C++ TESTS 50 93 204800 2900
30195248 F.Darcy D Sept. 8, 2017, 5:20 a.m. OK GNU C++ TESTS 50 93 51814400 2900
31111061 black_horse2014 D Oct. 7, 2017, 10:50 a.m. OK GNU C++11 TESTS 50 30 0 2900
69570079 HN-001 D Jan. 26, 2020, 1:49 p.m. OK GNU C++11 TESTS 50 31 0 2900
30210830 rajat1603 D Sept. 8, 2017, 6:51 p.m. OK GNU C++11 TESTS 50 31 0 2900
30095036 chitanda D Sept. 5, 2017, 9:05 a.m. OK GNU C++11 TESTS 50 31 0 2900
45433057 liumh8 D Nov. 8, 2018, 5:54 a.m. OK GNU C++11 TESTS 50 31 102400 2900
29993990 SirShokoladina D Sept. 1, 2017, 5:23 p.m. OK GNU C++11 TESTS 50 31 102400 2900
33636475 otrecnoc D Dec. 26, 2017, 5:12 a.m. OK GNU C++11 TESTS 50 31 2150400 2900
60421984 ezhjw D Sept. 12, 2019, 6:31 a.m. OK GNU C++11 TESTS 50 46 0 2900
51569709 _twilight D March 20, 2019, 11:09 a.m. OK GNU C++11 TESTS 50 46 0 2900
46529337 xielinhan D Dec. 3, 2018, 3:15 a.m. OK GNU C++11 TESTS 50 46 0 2900
30129162 mengrao D Sept. 6, 2017, 10:52 a.m. OK GNU C++14 TESTS 50 15 0 2900
30129130 mengrao D Sept. 6, 2017, 10:51 a.m. OK GNU C++14 TESTS 50 15 0 2900
30126034 mengrao D Sept. 6, 2017, 8:19 a.m. OK GNU C++14 TESTS 50 15 0 2900
30007753 FallDream D Sept. 2, 2017, 9:27 a.m. OK GNU C++14 TESTS 50 15 0 2900
29986436 ksun48 D Sept. 1, 2017, 2:58 p.m. OK GNU C++14 TESTS 50 15 0 2900
40980030 ReaLNero1 D July 30, 2018, 5:20 p.m. OK GNU C++14 TESTS 50 31 0 2900
30128988 mengrao D Sept. 6, 2017, 10:44 a.m. OK GNU C++14 TESTS 50 31 0 2900
29991292 aid D Sept. 1, 2017, 4:07 p.m. OK GNU C++14 TESTS 50 31 0 2900
29994776 namai D Sept. 1, 2017, 6:07 p.m. OK GNU C++14 TESTS 50 31 102400 2900
29983235 MiFaFaOvO D Sept. 1, 2017, 2:32 p.m. OK GNU C++14 TESTS 50 31 102400 2900
69570099 vjudge3 D Jan. 26, 2020, 1:49 p.m. OK GNU C++17 TESTS 50 31 0 2900
61956952 Roundgod D Oct. 6, 2019, 6:11 a.m. OK GNU C++17 TESTS 50 46 0 2900
46995145 ShichengXiao D Dec. 14, 2018, 7:54 a.m. OK GNU C++17 TESTS 50 46 0 2900
66899911 justfocusplease D Dec. 15, 2019, 4:53 a.m. OK GNU C++17 TESTS 50 46 102400 2900
44097157 zjp_shadow D Oct. 11, 2018, 2:13 a.m. OK GNU C++17 TESTS 50 46 409600 2900
69662987 vjudge2 D Jan. 28, 2020, 10:12 a.m. OK GNU C++17 TESTS 50 62 102400 2900
45149185 Benq D Oct. 31, 2018, 6:42 p.m. OK GNU C++17 TESTS 50 93 102400 2900
49438959 Shayan.P D Feb. 3, 2019, 8:01 p.m. OK GNU C++17 TESTS 50 109 307200 2900
30196316 uwi D Sept. 8, 2017, 6:41 a.m. OK Java 8 TESTS 50 109 0 2900
29992529 mmaxio D Sept. 1, 2017, 4:31 p.m. OK Java 8 TESTS 50 1341 0 2900
42536922 Doomsday_Singer D Sept. 6, 2018, 2:27 a.m. OK PyPy 3 TESTS 50 545 8908800 2900

remove filters

Back to search problems