Codeforces Round 1000 (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
2063 Codeforces Round 1000 (Div. 2) FINISHED False 7200 38858123 Jan. 22, 2025, 12:05 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 14529 ) C Remove Exactly Two PROGRAMMING brute force data structures dp graphs greedy sortings trees

You are given a tree(^{\text{∗}}) of (n) vertices. You must perform the following operation exactly twice . Select a vertex (v); Remove all edges incident to (v), and also the vertex (v). Please find the maximum number of connected components after performing the operation exactly twice . Two vertices (x) and (y) are in the same connected component if and only if there exists a path from (x) to (y). For clarity, note that the graph with (0) vertices has (0) connected components by definition.(^{\text{†}}) (^{\text{∗}})A tree is a connected graph without cycles. (^{\text{†}})But is such a graph connected? Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^4)). The description of the test cases follows. The first line of each test case contains a single integer (n) ((2 \le n \le 2 \cdot 10^5)). Each of the next (n-1) lines contains two integers (u_i) and (v_i), denoting the two vertices connected by an edge ((1 \le u_i,v_i \le n), (u_i \neq v_i)). It is guaranteed that the given edges form a tree. It is guaranteed that the sum of (n) over all test cases does not exceed (2 \cdot 10^5). For each test case, output the maximum number of connected components on a separate line. On the first test case, removing a vertex twice will make the graph empty. By definition, the number of connected components in the graph with (0) vertices is (0). Therefore, the answer is (0). On the second test case, removing two vertices (1) and (2) leaves (2) connected components. As it is impossible to make (3) connected components with (2) vertices, the answer is (2). On the third test case, removing two vertices (1) and (5) leaves (4) connected components, which are (\left\{ 2,4\right\}), (\left\{ 3\right\}), (\left\{ 6\right\}), and (\left\{ 7\right\}). It can be

Tutorials

Codeforces Round 1000 (Div. 2) — Editorial

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
302533278 AliRagab313 C Jan. 23, 2025, 1:56 a.m. OK C# 10 TESTS 23 437 30105600
302497257 Anastasiya_Andreevna C Jan. 22, 2025, 5:43 p.m. OK C# 10 TESTS 23 531 54272000
302531689 nbbwcff123 C Jan. 23, 2025, 1:31 a.m. OK C++17 (GCC 7-32) TESTS 23 124 1945600
302526571 Rainforests C Jan. 22, 2025, 11:59 p.m. OK C++17 (GCC 7-32) TESTS 23 139 5836800
302545426 JainUjjwal C Jan. 23, 2025, 4:49 a.m. OK C++17 (GCC 7-32) TESTS 26 140 4300800
302530384 neach_joup C Jan. 23, 2025, 1:10 a.m. OK C++17 (GCC 7-32) TESTS 23 140 5632000
302468363 sensei_ C Jan. 22, 2025, 3 p.m. OK C++17 (GCC 7-32) TESTS 21 155 307200
302530381 Gordios_knot C Jan. 23, 2025, 1:10 a.m. OK C++17 (GCC 7-32) TESTS 23 155 4915200
302467432 lvlian C Jan. 22, 2025, 2:57 p.m. OK C++17 (GCC 7-32) TESTS 21 156 102400
302500442 dlkr18 C Jan. 22, 2025, 6:04 p.m. OK C++17 (GCC 7-32) TESTS 23 156 307200
302471169 Liuxito2040 C Jan. 22, 2025, 3:13 p.m. OK C++17 (GCC 7-32) TESTS 21 156 1331200
302549734 Thelearned C Jan. 23, 2025, 5:41 a.m. OK C++17 (GCC 7-32) TESTS 26 156 6348800
302539662 xzczxczxc C Jan. 23, 2025, 3:31 a.m. OK C++20 (GCC 13-64) TESTS 26 124 1331200
302521094 RaghavChawla C Jan. 22, 2025, 9:47 p.m. OK C++20 (GCC 13-64) TESTS 23 124 5324800
302546266 gapbyam C Jan. 23, 2025, 4:59 a.m. OK C++20 (GCC 13-64) TESTS 26 140 1638400
302527520 upcalpha C Jan. 23, 2025, 12:18 a.m. OK C++20 (GCC 13-64) TESTS 23 140 48128000
302548023 ALLENN929 C Jan. 23, 2025, 5:20 a.m. OK C++20 (GCC 13-64) TESTS 26 140 50483200
302477486 the_escapist C Jan. 22, 2025, 3:44 p.m. OK C++20 (GCC 13-64) TESTS 22 155 1331200
302498448 Devdom C Jan. 22, 2025, 5:51 p.m. OK C++20 (GCC 13-64) TESTS 23 156 3379200
302541128 AChievedreaM C Jan. 23, 2025, 3:50 a.m. OK C++20 (GCC 13-64) TESTS 26 156 57753600
302543636 Miriin_the_morning C Jan. 23, 2025, 4:25 a.m. OK C++20 (GCC 13-64) TESTS 26 186 11264000
302531234 bras C Jan. 23, 2025, 1:24 a.m. OK C++20 (GCC 13-64) TESTS 23 186 11468800
302468274 rewhile C Jan. 22, 2025, 3 p.m. OK C++23 (GCC 14-64, msys2) TESTS 21 62 2150400
302484301 anuj_234 C Jan. 22, 2025, 4:24 p.m. OK C++23 (GCC 14-64, msys2) TESTS 23 124 6246400
302506322 abhi132 C Jan. 22, 2025, 6:45 p.m. OK C++23 (GCC 14-64, msys2) TESTS 23 139 7680000
302474276 honghaojin C Jan. 22, 2025, 3:27 p.m. OK C++23 (GCC 14-64, msys2) TESTS 21 155 4915200
302484565 ruby_0131 C Jan. 22, 2025, 4:26 p.m. OK C++23 (GCC 14-64, msys2) TESTS 23 155 6451200
302492821 Mitul_Aggarwal C Jan. 22, 2025, 5:17 p.m. OK C++23 (GCC 14-64, msys2) TESTS 23 156 95641600
302540027 LNian C Jan. 23, 2025, 3:36 a.m. OK C++23 (GCC 14-64, msys2) TESTS 26 171 8601600
302526443 destructor123 C Jan. 22, 2025, 11:56 p.m. OK C++23 (GCC 14-64, msys2) TESTS 23 171 13107200
302535358 JollyCowsHu C Jan. 23, 2025, 2:31 a.m. OK C++23 (GCC 14-64, msys2) TESTS 23 186 11980800
302469391 qingshangqaq C Jan. 22, 2025, 3:05 p.m. OK C++23 (GCC 14-64, msys2) TESTS 21 187 4915200
302472395 redreoicy C Jan. 22, 2025, 3:18 p.m. OK Java 21 TESTS 21 718 35532800
302496711 jai_hanumant C Jan. 22, 2025, 5:40 p.m. OK Java 21 TESTS 23 718 65228800
302549761 emme C Jan. 23, 2025, 5:41 a.m. OK Java 21 TESTS 26 750 35430400
302494745 jai_hanumant C Jan. 22, 2025, 5:28 p.m. OK Java 21 TESTS 23 764 65638400
302538819 Zhanzhe_Lee C Jan. 23, 2025, 3:20 a.m. OK Java 21 TESTS 25 796 55808000
302532568 anay293 C Jan. 23, 2025, 1:45 a.m. OK Java 21 TESTS 23 858 32972800
302460522 dineshdcoc C Jan. 22, 2025, 2:03 p.m. OK Java 21 TESTS 21 890 36147200
302539740 akshatsaxena552004.ss C Jan. 23, 2025, 3:32 a.m. OK Java 21 TESTS 26 921 123596800
302473136 sulabhambule C Jan. 22, 2025, 3:22 p.m. OK Java 21 TESTS 21 937 55910400
302538006 emme C Jan. 23, 2025, 3:10 a.m. OK Java 21 TESTS 25 968 67276800
302504418 kamranm C Jan. 22, 2025, 6:31 p.m. OK Java 8 TESTS 23 749 254054400
302548652 InfinityX C Jan. 23, 2025, 5:28 a.m. OK Java 8 TESTS 26 905 61132800
302474432 CipherSphinx_Raj C Jan. 22, 2025, 3:28 p.m. OK Java 8 TESTS 21 905 163635200
302474259 __runknowna__ C Jan. 22, 2025, 3:27 p.m. OK Java 8 TESTS 21 905 163635200
302512839 ne_prajwal C Jan. 22, 2025, 7:44 p.m. OK Java 8 TESTS 23 1468 69939200
302501129 L1419GHT C Jan. 22, 2025, 6:09 p.m. OK Java 8 TESTS 23 1514 50585600
302469058 CodeWode C Jan. 22, 2025, 3:03 p.m. OK Java 8 TESTS 21 1515 37171200
302515147 ne_prajwal C Jan. 22, 2025, 8:12 p.m. OK Java 8 TESTS 23 1531 69734400
302514971 ne_prajwal C Jan. 22, 2025, 8:10 p.m. OK Java 8 TESTS 23 1592 69939200
302512129 ne_prajwal C Jan. 22, 2025, 7:37 p.m. OK Java 8 TESTS 23 1609 69734400
302460278 hecker422 C Jan. 22, 2025, 2:03 p.m. OK Kotlin 1.9 TESTS 21 780 37990400
302537864 Swan416 C Jan. 23, 2025, 3:08 a.m. OK Kotlin 1.9 TESTS 25 1233 34304000
302473582 TitTolkachev C Jan. 22, 2025, 3:24 p.m. OK Kotlin 1.9 TESTS 21 1265 117657600
302470168 jagbarrameda C Jan. 22, 2025, 3:08 p.m. OK Kotlin 1.9 TESTS 21 1437 132812800
302469397 ahtoh_ C Jan. 22, 2025, 3:05 p.m. OK Node.js TESTS 21 1109 155340800
302469697 FourthRateOne C Jan. 22, 2025, 3:06 p.m. OK PyPy 3 TESTS 21 1343 62156800
302461081 AtonDomRanyug C Jan. 22, 2025, 2:04 p.m. OK PyPy 3 TESTS 21 1593 30310400
302521996 smilence C Jan. 22, 2025, 10:05 p.m. OK PyPy 3-64 TESTS 23 265 46489600
302521866 smilence C Jan. 22, 2025, 10:02 p.m. OK PyPy 3-64 TESTS 23 327 46387200
302515900 gardengnome C Jan. 22, 2025, 8:22 p.m. OK PyPy 3-64 TESTS 23 358 47001600
302516041 gardengnome C Jan. 22, 2025, 8:24 p.m. OK PyPy 3-64 TESTS 23 359 47104000
302528991 RobinFromTheHood C Jan. 23, 2025, 12:45 a.m. OK PyPy 3-64 TESTS 23 374 38502400
302468618 Apoko C Jan. 22, 2025, 3:01 p.m. OK PyPy 3-64 TESTS 21 437 37580800
302525045 SoleProprietor C Jan. 22, 2025, 11:18 p.m. OK PyPy 3-64 TESTS 23 483 52326400
302491693 nather73 C Jan. 22, 2025, 5:10 p.m. OK PyPy 3-64 TESTS 23 562 53350400
302524581 SoleProprietor C Jan. 22, 2025, 11:04 p.m. OK PyPy 3-64 TESTS 23 593 70348800
302514567 ossau C Jan. 22, 2025, 8:05 p.m. OK PyPy 3-64 TESTS 23 609 54784000
302476879 iska_terminator C Jan. 22, 2025, 3:41 p.m. OK Python 3 TESTS 22 843 84275200
302480146 23110276 C Jan. 22, 2025, 3:59 p.m. OK Python 3 TESTS 23 859 47616000
302467530 the_seal C Jan. 22, 2025, 2:57 p.m. OK Python 3 TESTS 21 859 88166400
302498614 SS_CM C Jan. 22, 2025, 5:52 p.m. OK Python 3 TESTS 23 1390 63283200
302498024 SS_CM C Jan. 22, 2025, 5:48 p.m. OK Python 3 TESTS 23 1468 63590400
302461358 Fgdg45 C Jan. 22, 2025, 2:04 p.m. OK Python 3 TESTS 21 1671 105881600
302496883 Competive_Programmer C Jan. 22, 2025, 5:41 p.m. OK Rust 2021 TESTS 23 140 32665600
302521124 vstiff C Jan. 22, 2025, 9:48 p.m. OK Rust 2021 TESTS 23 202 62566400
302483609 kalinov C Jan. 22, 2025, 4:20 p.m. OK Rust 2021 TESTS 23 296 45568000
302484230 bibimoni C Jan. 22, 2025, 4:23 p.m. OK Rust 2021 TESTS 23 515 23040000

remove filters

Back to search problems