Codeforces Round 576 (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
1198 Codeforces Round 576 (Div. 1) FINISHED False 7200 167325899 July 30, 2019, 2:35 p.m.

Problems

Solved$
Index
Name
Type
Tags
Community Tag
Rating
( 3591 ) C Matching vs Independent Set PROGRAMMING constructive algorithms graphs greedy sortings 2200

B'You are given a graph with 3 cdot n vertices and m edges. You are to find a matching of n edges, or an independent set of n vertices. A set of edges is called a matching if no two edges share an endpoint. A set of vertices is called an independent set if no two vertices are connected with an edge. The first line contains a single integer T ge 1 -- the number of graphs you need to process. The description of T graphs follows. The first line of description of a single graph contains two integers n and m , where 3 cdot n is the number of vertices, and m is the number of edges in the graph ( 1 <= q n <= q 10^{5} , 0 <= q m <= q 5 cdot 10^{5} ). Each of the next m lines contains two integers v_i and u_i ( 1 <= q v_i, u_i <= q 3 cdot n ), meaning that there is an edge between vertices v_i and u_i . It is guaranteed that there are no self-loops and no multiple edges in the graph. It is guaranteed that the sum of all n over all graphs in a single test does not exceed 10^{5} , and the sum of all m over all graphs in a single test does not exceed 5 cdot 10^{5} . Print your answer for each of the T graphs. Output your answer for a single graph in the following format. If you found a matching of size n , on the first line print "Matching" (without quotes), and on the second line print n integers -- the indices of the edges in the matching. The edges are numbered from 1 to m in the input order. If you found an independent set of size n , on the first line print "IndSet" (without quotes), and on the second line print n integers -- the indices of the vertices in the independent set. If there is no matching and no independent set of the specified size, print "Impossible" (without quotes). You can print edges and vertices in any order. If there are several solutions, print any. In particular, if there'...

Tutorials

E

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
58002894 yosupo C July 30, 2019, 2:57 p.m. OK D TESTS 103 155 4198400 2200
58003284 hos.lyric C July 30, 2019, 2:58 p.m. OK D TESTS 103 374 11980800 2200
58014846 Gassa C July 30, 2019, 3:32 p.m. OK D TESTS 103 420 24985600 2200
58113807 MajAK C Aug. 1, 2019, 8:11 a.m. OK GNU C11 TESTS 107 936 3174400 2200
58857308 luogu_bot5 C Aug. 15, 2019, 9:54 a.m. OK GNU C++11 TESTS 108 46 1536000 2200
58861790 C20200904 C Aug. 15, 2019, 11:55 a.m. OK GNU C++11 TESTS 108 46 1536000 2200
58361722 luogu_bot5 C Aug. 6, 2019, 1:10 a.m. OK GNU C++11 TESTS 108 46 2048000 2200
58692670 Depth_First_Search C Aug. 13, 2019, 4:14 a.m. OK GNU C++11 TESTS 108 46 3481600 2200
60589616 luogu_bot3 C Sept. 15, 2019, 12:53 a.m. OK GNU C++11 TESTS 108 46 18022400 2200
58178014 shuyingte C Aug. 2, 2019, 1:54 p.m. OK GNU C++11 TESTS 108 61 1126400 2200
58314638 lsroi C Aug. 5, 2019, 2:11 a.m. OK GNU C++11 TESTS 108 61 1536000 2200
58223416 Zechariah_2001 C Aug. 3, 2019, 1:29 p.m. OK GNU C++11 TESTS 108 61 2048000 2200
58856637 luogu_bot2 C Aug. 15, 2019, 9:35 a.m. OK GNU C++11 TESTS 108 61 2048000 2200
61681371 ProgSlacking C Oct. 2, 2019, 1:22 a.m. OK GNU C++11 TESTS 108 61 6348800 2200
61856995 noticeMeSempai C Oct. 4, 2019, 2:19 p.m. OK GNU C++14 TESTS 108 61 1536000 2200
58172027 tokitsukaze C Aug. 2, 2019, 11:43 a.m. OK GNU C++14 TESTS 108 62 2355200 2200
58119481 Libitina C Aug. 1, 2019, 10:07 a.m. OK GNU C++14 TESTS 107 139 2252800 2200
58112491 vjudge2 C Aug. 1, 2019, 7:44 a.m. OK GNU C++14 TESTS 107 140 2252800 2200
58117831 Libitina C Aug. 1, 2019, 9:30 a.m. OK GNU C++14 TESTS 107 155 2252800 2200
58291038 ghanta88 C Aug. 4, 2019, 5:35 p.m. OK GNU C++14 TESTS 108 155 2252800 2200
58014487 Linkus C July 30, 2019, 3:31 p.m. OK GNU C++14 TESTS 103 155 16076800 2200
58010486 Localization C July 30, 2019, 3:18 p.m. OK GNU C++14 TESTS 103 171 1433600 2200
58670387 rhrnald C Aug. 12, 2019, 2:12 p.m. OK GNU C++14 TESTS 108 171 26624000 2200
65003743 zycmx C Nov. 15, 2019, 4:57 a.m. OK GNU C++14 TESTS 108 186 2355200 2200
58051153 F.J C July 31, 2019, 2:41 a.m. OK GNU C++17 TESTS 105 46 6860800 2200
58046393 Unsterblicher_Geist C July 30, 2019, 11:57 p.m. OK GNU C++17 TESTS 105 62 4608000 2200
58014744 YogayoG C July 30, 2019, 3:31 p.m. OK GNU C++17 TESTS 103 171 2048000 2200
58014635 nishank.suresh C July 30, 2019, 3:31 p.m. OK GNU C++17 TESTS 103 171 2969600 2200
58020229 GoogleBot C July 30, 2019, 3:50 p.m. OK GNU C++17 TESTS 103 171 7884800 2200
58039174 srikkanthr C July 30, 2019, 6:56 p.m. OK GNU C++17 TESTS 103 171 13107200 2200
58016677 indy256 C July 30, 2019, 3:38 p.m. OK GNU C++17 TESTS 103 186 1126400 2200
58005820 danya.smelskiy C July 30, 2019, 3:05 p.m. OK GNU C++17 TESTS 103 186 1433600 2200
58006777 Rzepa C July 30, 2019, 3:07 p.m. OK GNU C++17 TESTS 103 186 2048000 2200
58001059 mnbvmar C July 30, 2019, 2:53 p.m. OK GNU C++17 TESTS 103 186 3788800 2200
58344246 WangJialei C Aug. 5, 2019, 2:20 p.m. OK Go TESTS 108 608 29081600 2200
59190716 beginner1010 C Aug. 20, 2019, 8:54 p.m. OK Java 8 TESTS 108 155 0 2200
58131659 uwi C Aug. 1, 2019, 2:30 p.m. OK Java 8 TESTS 107 170 0 2200
65305065 aminul C Nov. 18, 2019, 2:34 p.m. OK Java 8 TESTS 108 171 1536000 2200
58005782 Egor C July 30, 2019, 3:05 p.m. OK Java 8 TESTS 103 187 0 2200
58041618 tmwilliamlin168 C July 30, 2019, 7:57 p.m. OK Java 8 TESTS 104 202 5222400 2200
58025785 dalt C July 30, 2019, 4:10 p.m. OK Java 8 TESTS 103 202 5222400 2200
58024583 niyaznigmatul C July 30, 2019, 4:05 p.m. OK Java 8 TESTS 103 233 0 2200
58940018 happybelly C Aug. 17, 2019, 6:30 a.m. OK Java 8 TESTS 108 249 0 2200
57999787 Petr C July 30, 2019, 2:50 p.m. OK Java 8 TESTS 103 249 0 2200
58109179 AnandOza C Aug. 1, 2019, 6:15 a.m. OK Java 8 TESTS 107 265 0 2200
58459813 darnley C Aug. 8, 2019, 3:43 p.m. OK Kotlin TESTS 108 889 5427200 2200
58351003 darnley C Aug. 5, 2019, 5:10 p.m. OK Kotlin TESTS 108 904 5324800 2200
58035370 claw88 C July 30, 2019, 5:57 p.m. OK Mono C# TESTS 103 327 10854400 2200
58009928 riantkb C July 30, 2019, 3:17 p.m. OK Mono C# TESTS 103 358 13414400 2200
58494450 vjudge4 C Aug. 9, 2019, 11:31 a.m. OK MS C++ TESTS 108 139 3993600 2200
58538414 vjudge4 C Aug. 10, 2019, 1 p.m. OK MS C++ TESTS 108 140 3174400 2200
62254218 vjudge5 C Oct. 10, 2019, 10:17 a.m. OK MS C++ TESTS 108 155 3993600 2200
61103080 math957963 C Sept. 23, 2019, 7:49 a.m. OK MS C++ TESTS 108 171 1126400 2200
58036870 Milanin C July 30, 2019, 6:15 p.m. OK MS C++ 2017 TESTS 103 234 7987200 2200
68852547 AleksanderBalobanov C Jan. 15, 2020, 9:30 a.m. OK MS C++ 2017 TESTS 108 280 14336000 2200
58027618 P___ C July 30, 2019, 4:17 p.m. OK MS C++ 2017 TESTS 103 546 38707200 2200
58268459 TOXait C Aug. 4, 2019, 3:44 p.m. OK MS C++ 2017 TESTS 108 670 5017600 2200
58063034 P___ C July 31, 2019, 8:03 a.m. OK MS C++ 2017 TESTS 105 670 54169600 2200
58097077 indy256 C July 31, 2019, 8:34 p.m. OK MS C++ 2017 TESTS 107 795 54476800 2200
58043813 drd93 C July 30, 2019, 9:20 p.m. OK PyPy 2 TESTS 104 420 40038400 2200
58972722 yumtam C Aug. 17, 2019, 9:30 p.m. OK PyPy 2 TESTS 108 467 41984000 2200
58086087 pajenegod C July 31, 2019, 3:40 p.m. OK PyPy 2 TESTS 106 467 49049600 2200
58043590 drd93 C July 30, 2019, 9:11 p.m. OK PyPy 2 TESTS 104 498 59801600 2200
58086142 pajenegod C July 31, 2019, 3:41 p.m. OK PyPy 3 TESTS 106 561 42803200 2200
69302068 meowmeow321 C Jan. 22, 2020, 2:07 p.m. OK PyPy 3 TESTS 108 873 11059200 2200
58037929 whatshisbucket C July 30, 2019, 6:31 p.m. OK PyPy 3 TESTS 103 889 23654400 2200
58038103 whatshisbucket C July 30, 2019, 6:34 p.m. OK PyPy 3 TESTS 103 920 26112000 2200
58018561 Kiri8128 C July 30, 2019, 3:44 p.m. OK PyPy 3 TESTS 103 966 28672000 2200
58530420 macleChen C Aug. 10, 2019, 9:13 a.m. OK PyPy 3 TESTS 108 997 11673600 2200
58515668 malylesio C Aug. 9, 2019, 11:01 p.m. OK PyPy 3 TESTS 108 998 11571200 2200
58876724 Helli.code C Aug. 15, 2019, 6:16 p.m. OK Python 2 TESTS 108 873 53657600 2200
58551308 shahed_shd C Aug. 10, 2019, 8:07 p.m. OK Python 3 TESTS 108 608 46080000 2200
58015688 EbTech C July 30, 2019, 3:34 p.m. OK Rust TESTS 103 78 716800 2200
58077672 YeXiaoRain C July 31, 2019, 12:54 p.m. OK Rust TESTS 106 217 1331200 2200
58087477 kobae964 C July 31, 2019, 4:12 p.m. OK Rust TESTS 106 405 20275200 2200

remove filters

Back to search problems