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 | 38944484 | Jan. 22, 2025, 12:05 p.m. |
Solved |
Index |
Name |
Type |
Tags |
Community Tag |
Rating |
|---|---|---|---|---|---|---|
| ( 14534 ) | 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 |
| Codeforces Round 1000 (Div. 2) — Editorial |
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 |
Back to search problems