Codeforces Round 581 (Div. 2)

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
1204 Codeforces Round 581 (Div. 2) FINISHED False 7200 171127487 Aug. 20, 2019, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 6786 ) C Anna, Svyatoslav and Maps PROGRAMMING dp graphs greedy shortest paths 1700

B"The main characters have been omitted to be short. You are given a directed unweighted graph without loops with n vertexes and a path in it (that path is not necessary simple) given by a sequence p_1, p_2, ldots, p_m of m vertexes; for each 1 <= q i < m there is an arc from p_i to p_{i+1} . Define the sequence v_1, v_2, ldots, v_k of k vertexes as good, if v is a subsequence of p , v_1 = p_1 , v_k = p_m , and p is one of the shortest paths passing through the vertexes v_1 , ldots , v_k in that order. A sequence a is a subsequence of a sequence b if a can be obtained from b by deletion of several (possibly, zero or all) elements. It is obvious that the sequence p is good but your task is to find the shortest good subsequence. If there are multiple shortest good subsequences, output any of them. The first line contains a single integer n ( 2 <= n <= 100 ) -- the number of vertexes in a graph. The next n lines define the graph by an adjacency matrix: the j -th character in the i -st line is equal to 1 if there is an arc from vertex i to the vertex j else it is equal to 0 . It is guaranteed that the graph doesn't contain loops. The next line contains a single integer m ( 2 <= m <= 10^6 ) -- the number of vertexes in the path. The next line contains m integers p_1, p_2, ldots, p_m ( 1 <= p_i <= n ) -- the sequence of vertexes in the path. It is guaranteed that for any 1 <= q i < m there is an arc from p_i to p_{i+1} . In the first line output a single integer k ( 2 <= q k <= q m ) -- the length of the shortest good subsequence. In the second line output k integers v_1 , ldots , v_k ( 1 <= q v_i <= q n ) -- the vertexes in the subsequence. If there are multiple shortest subsequences, print any."...

Tutorials

69244

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
59172614 daut-dlang C Aug. 20, 2019, 3:55 p.m. OK D TESTS 30 1575 44236800 1700
59186384 ruban C Aug. 20, 2019, 6:46 p.m. OK Delphi TESTS 33 218 197734400 1700
59210903 bdcaknoip C Aug. 21, 2019, 8:31 a.m. OK GNU C++11 TESTS 38 46 8089600 1700
59197248 luogu_bot4 C Aug. 21, 2019, 2:23 a.m. OK GNU C++11 TESTS 33 46 8089600 1700
59197191 Harurah C Aug. 21, 2019, 2:21 a.m. OK GNU C++11 TESTS 33 46 8089600 1700
59220041 BeNoble C Aug. 21, 2019, 11:53 a.m. OK GNU C++11 TESTS 47 46 14336000 1700
59182676 BeNoble C Aug. 20, 2019, 5:33 p.m. OK GNU C++11 TESTS 31 46 14336000 1700
59202898 chenyewei_1234 C Aug. 21, 2019, 5:46 a.m. OK GNU C++11 TESTS 34 61 8089600 1700
59182564 BeNoble C Aug. 20, 2019, 5:32 p.m. OK GNU C++11 TESTS 30 61 14336000 1700
59230738 bdcaknoip C Aug. 21, 2019, 3:22 p.m. OK GNU C++11 TESTS 48 62 8089600 1700
59162428 ChthollyNotaSeniorious C Aug. 20, 2019, 3:17 p.m. OK GNU C++11 TESTS 30 62 10342400 1700
59255905 pufanyi C Aug. 22, 2019, 6:37 a.m. OK GNU C++11 TESTS 55 62 16384000 1700
60370466 wleung_bvg C Sept. 11, 2019, 1:16 a.m. OK GNU C++14 TESTS 55 62 6656000 1700
59254883 disangan233 C Aug. 22, 2019, 6:09 a.m. OK GNU C++14 TESTS 55 62 24473600 1700
59535106 tokitsukaze C Aug. 26, 2019, 4:36 p.m. OK GNU C++14 TESTS 55 124 8396800 1700
59576385 Nyaan C Aug. 27, 2019, 2:18 p.m. OK GNU C++14 TESTS 55 218 8192000 1700
59262510 frost_ C Aug. 22, 2019, 9:11 a.m. OK GNU C++14 TESTS 55 218 10547200 1700
59223276 Ausmosian C Aug. 21, 2019, 12:58 p.m. OK GNU C++14 TESTS 48 218 10547200 1700
59217102 fuad036 C Aug. 21, 2019, 10:46 a.m. OK GNU C++14 TESTS 43 233 5222400 1700
59182333 ChandanAkiti C Aug. 20, 2019, 5:29 p.m. OK GNU C++14 TESTS 30 233 5222400 1700
59162835 BjbEfMbJmgpTvmuDjvebuj C Aug. 20, 2019, 3:19 p.m. OK GNU C++14 TESTS 30 233 5222400 1700
59204833 kumaraditya1999 C Aug. 21, 2019, 6:32 a.m. OK GNU C++14 TESTS 34 233 8192000 1700
59352935 interestingLSY C Aug. 23, 2019, 12:29 p.m. OK GNU C++17 TESTS 55 139 7475200 1700
60756831 vjudge3 C Sept. 18, 2019, 9:20 a.m. OK GNU C++17 TESTS 55 139 10035200 1700
59613462 pa123456 C Aug. 28, 2019, 11:47 a.m. OK GNU C++17 TESTS 55 155 18534400 1700
59192379 misanthrop.vg C Aug. 20, 2019, 10:18 p.m. OK GNU C++17 TESTS 33 218 8192000 1700
59191311 wjli C Aug. 20, 2019, 9:22 p.m. OK GNU C++17 TESTS 33 218 8192000 1700
69567165 Miracle_boY C Jan. 26, 2020, 12:51 p.m. OK GNU C++17 TESTS 55 218 10547200 1700
59264413 apurva9 C Aug. 22, 2019, 9:59 a.m. OK GNU C++17 TESTS 55 218 10547200 1700
59187244 new_bie_always C Aug. 20, 2019, 7:06 p.m. OK GNU C++17 TESTS 33 218 10547200 1700
59186223 ironic C Aug. 20, 2019, 6:42 p.m. OK GNU C++17 TESTS 33 218 10547200 1700
59950031 rschwan C Sept. 3, 2019, 2:13 p.m. OK GNU C++17 TESTS 55 233 4300800 1700
59546017 reanimatorzon C Aug. 26, 2019, 9:58 p.m. OK Go TESTS 55 124 12492800 1700
59167887 caidodo0_0 C Aug. 20, 2019, 3:35 p.m. OK Go TESTS 30 577 23244800 1700
66658363 Russell_Emerine C Dec. 12, 2019, 2:19 a.m. OK Haskell TESTS 55 1481 19046400 1700
59544029 mrmaximuzz C Aug. 26, 2019, 8:25 p.m. OK Haskell TESTS 55 1528 84172800 1700
59179961 jmazon C Aug. 20, 2019, 4:31 p.m. OK Haskell TESTS 30 1747 72601600 1700
60254348 ykt836 C Sept. 8, 2019, 8:37 a.m. OK Java 8 TESTS 55 171 18227200 1700
59171517 avijit_agarwal C Aug. 20, 2019, 3:50 p.m. OK Java 8 TESTS 30 202 20172800 1700
59190968 hot.potato C Aug. 20, 2019, 9:06 p.m. OK Java 8 TESTS 33 217 20070400 1700
59244094 amotoma3 C Aug. 21, 2019, 9:45 p.m. OK Java 8 TESTS 49 217 21811200 1700
59171948 Shae C Aug. 20, 2019, 3:52 p.m. OK Java 8 TESTS 30 249 2969600 1700
59848579 saurabh0611 C Sept. 1, 2019, 10:32 a.m. OK Java 8 TESTS 55 249 3379200 1700
59173906 qlf9 C Aug. 20, 2019, 4:01 p.m. OK Java 8 TESTS 30 249 16998400 1700
65253997 procrastinate7 C Nov. 17, 2019, 12:52 p.m. OK Java 8 TESTS 55 249 23142400 1700
59260935 chojh1222 C Aug. 22, 2019, 8:35 a.m. OK Java 8 TESTS 55 264 5529600 1700
59208570 arnavks97 C Aug. 21, 2019, 7:47 a.m. OK Java 8 TESTS 37 264 20172800 1700
59972142 vjudge3 C Sept. 4, 2019, 2:32 a.m. OK Kotlin TESTS 55 405 15872000 1700
59662255 Benq C Aug. 29, 2019, 12:57 p.m. OK Kotlin TESTS 55 655 67481600 1700
59198379 Spheniscine C Aug. 21, 2019, 3:02 a.m. OK Kotlin TESTS 33 686 65638400 1700
59201754 Tlatoani C Aug. 21, 2019, 5:15 a.m. OK Kotlin TESTS 34 1435 21094400 1700
59201322 Tlatoani C Aug. 21, 2019, 5 a.m. OK Kotlin TESTS 34 1435 21094400 1700
59182797 kuuso C Aug. 20, 2019, 5:35 p.m. OK Mono C# TESTS 31 421 77209600 1700
60530900 eki C Sept. 14, 2019, 12:25 p.m. OK Mono C# TESTS 55 436 61952000 1700
59253826 og.kostya C Aug. 22, 2019, 5:36 a.m. OK Mono C# TESTS 55 467 17100800 1700
59163294 keymoon C Aug. 20, 2019, 3:20 p.m. OK Mono C# TESTS 30 467 88268800 1700
59165354 claw88 C Aug. 20, 2019, 3:26 p.m. OK Mono C# TESTS 30 514 69324800 1700
59167754 omikad C Aug. 20, 2019, 3:35 p.m. OK Mono C# TESTS 30 670 84275200 1700
59217510 camypaper C Aug. 21, 2019, 10:56 a.m. OK Mono C# TESTS 43 1668 144896000 1700
59197369 vjudge3 C Aug. 21, 2019, 2:27 a.m. OK MS C++ TESTS 33 265 5222400 1700
62616565 vjudge3 C Oct. 15, 2019, 11:36 a.m. OK MS C++ TESTS 55 265 8089600 1700
59197705 vjudge2 C Aug. 21, 2019, 2:38 a.m. OK MS C++ TESTS 33 265 8089600 1700
59197989 yznl C Aug. 21, 2019, 2:48 a.m. OK MS C++ TESTS 33 265 8192000 1700
59173549 kevin19984 C Aug. 20, 2019, 4 p.m. OK MS C++ TESTS 30 280 1126400 1700
69466712 vjudge5 C Jan. 24, 2020, 1:08 p.m. OK MS C++ TESTS 55 280 8089600 1700
60780084 vjudge2 C Sept. 18, 2019, 3:57 p.m. OK MS C++ TESTS 55 280 8089600 1700
59249902 NPUlzh C Aug. 22, 2019, 3:03 a.m. OK MS C++ TESTS 51 280 8089600 1700
59198051 yznl C Aug. 21, 2019, 2:50 a.m. OK MS C++ TESTS 33 280 8192000 1700
59201585 vjudge5 C Aug. 21, 2019, 5:09 a.m. OK MS C++ TESTS 34 296 8089600 1700
59197535 Saber_Altria C Aug. 21, 2019, 2:33 a.m. OK MS C++ 2017 TESTS 33 374 5222400 1700
59195160 succ1815406055 C Aug. 21, 2019, 1:06 a.m. OK MS C++ 2017 TESTS 33 389 8089600 1700
59177599 21181522 C Aug. 20, 2019, 4:20 p.m. OK MS C++ 2017 TESTS 30 389 8089600 1700
59512322 guoriyue C Aug. 26, 2019, 8:28 a.m. OK MS C++ 2017 TESTS 55 389 8089600 1700
59512056 guoriyue C Aug. 26, 2019, 8:22 a.m. OK MS C++ 2017 TESTS 55 389 9318400 1700
59262607 pmitkov C Aug. 22, 2019, 9:13 a.m. OK MS C++ 2017 TESTS 55 389 11980800 1700
59164282 euqrry C Aug. 20, 2019, 3:23 p.m. OK MS C++ 2017 TESTS 30 390 3993600 1700
59197090 VagrantAC C Aug. 21, 2019, 2:19 a.m. OK MS C++ 2017 TESTS 33 390 8089600 1700
59378599 zhangwen123 C Aug. 24, 2019, 12:53 a.m. OK MS C++ 2017 TESTS 55 405 16281600 1700
61412030 shebao C Sept. 28, 2019, 9:02 a.m. OK MS C++ 2017 TESTS 55 420 12083200 1700
61067796 gsteph C Sept. 22, 2019, 11:40 a.m. OK PyPy 2 TESTS 55 405 49766400 1700
59365692 thuutin C Aug. 23, 2019, 5:04 p.m. OK PyPy 2 TESTS 55 405 57139200 1700
59167746 TheManTheMythTheLegend C Aug. 20, 2019, 3:35 p.m. OK PyPy 2 TESTS 30 452 67379200 1700
59166038 yumtam C Aug. 20, 2019, 3:29 p.m. OK PyPy 2 TESTS 30 483 67788800 1700
59171676 c1729 C Aug. 20, 2019, 3:51 p.m. OK PyPy 2 TESTS 30 514 62361600 1700
59498951 petabyte0 C Aug. 26, 2019, 1:17 a.m. OK PyPy 2 TESTS 55 608 77721600 1700
59172141 Mukundan314 C Aug. 20, 2019, 3:53 p.m. OK PyPy 2 TESTS 30 873 46182400 1700
59389929 sm1ley C Aug. 24, 2019, 8:03 a.m. OK PyPy 3 TESTS 55 561 85299200 1700
59166574 algmyr C Aug. 20, 2019, 3:30 p.m. OK PyPy 3 TESTS 30 638 74035200 1700
59533476 erickjohnross C Aug. 26, 2019, 3:58 p.m. OK PyPy 3 TESTS 55 826 60518400 1700
60047252 nagato1208 C Sept. 4, 2019, 9:13 p.m. OK PyPy 3 TESTS 55 841 63897600 1700
59973909 nagato1208 C Sept. 4, 2019, 4:29 a.m. OK PyPy 3 TESTS 55 842 63795200 1700
59187008 karan_1244 C Aug. 20, 2019, 7 p.m. OK PyPy 3 TESTS 33 842 64819200 1700
61861443 wattaihei C Oct. 4, 2019, 3:27 p.m. OK PyPy 3 TESTS 55 857 59596800 1700
59879327 bandi.enkh C Sept. 2, 2019, 3:26 a.m. OK PyPy 3 TESTS 55 857 74035200 1700
59186849 lpm C Aug. 20, 2019, 6:57 p.m. OK PyPy 3 TESTS 33 858 65024000 1700
59180150 CHelle C Aug. 20, 2019, 4:32 p.m. OK PyPy 3 TESTS 30 873 58880000 1700
59213163 kaif_7 C Aug. 21, 2019, 9:12 a.m. OK Python 2 TESTS 38 1684 32563200 1700
59175374 shubhankarsharma00 C Aug. 20, 2019, 4:08 p.m. OK Python 2 TESTS 30 1793 32051200 1700
59527313 erickjohnross C Aug. 26, 2019, 1:49 p.m. OK Python 3 TESTS 55 1653 51507200 1700
69430079 Munchy_1 dazlersan1 vaisnav C Jan. 23, 2020, 5:03 p.m. OK Python 3 TESTS 55 1716 51916800 1700
60898795 chgliu C Sept. 19, 2019, 8:02 p.m. OK Python 3 TESTS 55 1824 66867200 1700
59274867 kushaan C Aug. 22, 2019, 2:13 p.m. OK Python 3 TESTS 55 1965 51814400 1700
59274560 kushaan C Aug. 22, 2019, 2:05 p.m. OK Python 3 TESTS 55 1981 51814400 1700
59389572 sm1ley C Aug. 24, 2019, 7:54 a.m. OK Python 3 TESTS 55 1996 50073600 1700
59517153 suminos C Aug. 26, 2019, 10:34 a.m. OK Rust TESTS 55 139 43520000 1700
59177481 manta1130 C Aug. 20, 2019, 4:19 p.m. OK Rust TESTS 30 265 11571200 1700
59172503 arzk C Aug. 20, 2019, 3:55 p.m. OK Rust TESTS 30 280 10444800 1700
59903943 aeiou1 C Sept. 2, 2019, 2:37 p.m. OK Rust TESTS 55 451 23142400 1700
59457360 ValenKof C Aug. 25, 2019, 2:53 p.m. OK Rust TESTS 55 468 36454400 1700
59261562 chankyin C Aug. 22, 2019, 8:50 a.m. OK Rust TESTS 55 530 59801600 1700
59262033 chankyin C Aug. 22, 2019, 9 a.m. OK Rust TESTS 55 545 52940800 1700
59262150 chankyin C Aug. 22, 2019, 9:02 a.m. OK Rust TESTS 55 576 52940800 1700

remove filters

Back to search problems