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.
Problems
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
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