Codeforces Round 976 (Div. 2) and Divide By Zero 9.0

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
2020 Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 FINISHED False 7200 48781523 Sept. 29, 2024, 3:35 p.m.

Problems

Solved
Index
Name
Type
Tags
Community Tag
Rating
( 7392 ) D Connect the Dots PROGRAMMING brute force dfs and similar dp dsu graphs math trees

One fine evening, Alice sat down to play the classic game "Connect the Dots", but with a twist. To play the game, Alice draws a straight line and marks (n) points on it, indexed from (1) to (n). Initially, there are no arcs between the points, so they are all disjoint. After that, Alice performs (m) operations of the following type: She picks three integers (a_i), (d_i) ((1 \le d_i \le 10)), and (k_i). She selects points (a_i, a_i+d_i, a_i+2d_i, a_i+3d_i, \ldots, a_i+k_i\cdot d_i) and connects each pair of these points with arcs. After performing all (m) operations, she wants to know the number of connected components(^\dagger) these points form. Please help her find this number. (^\dagger) Two points are said to be in one connected component if there is a path between them via several (possibly zero) arcs and other points. Each test contains multiple test cases. The first line contains the number of test cases (t) ((1 \le t \le 10^5)). The description of the test cases follows. The first line of each test case contains two integers (n) and (m) ((1 \le n \le 2 \cdot 10^5), (1 \le m \le 2 \cdot 10^5)). The (i)-th of the following (m) lines contains three integers (a_i), (d_i), and (k_i) ((1 \le a_i \le a_i + k_i\cdot d_i \le n), (1 \le d_i \le 10), (0 \le k_i \le n)). It is guaranteed that both the sum of (n) and the sum of (m) over all test cases do not exceed (2 \cdot 10^5). For each test case, output the number of connected components. In the first test case, there are (n = 10) points. The first operation joins the points (1), (3), (5), (7), and (9). The second operation joins the points (2), (4), (6), (8), and (10). There are thus two connected components: (\{1, 3, 5, 7, 9\}) and (\{2, 4, 6, 8, 10\}). In the second test case, there are (n = 100) points. The only operation joins the po

Tutorials

Tutorial for Codeforces Round 976 (Div. 2) and Divide By Zero 9.0

Submissions

Submission Id
Author(s)
Index
Submitted
Verdict
Language
Test Set
Tests Passed
Time taken (ms)
Memory Consumed (bytes)
Tags
Rating
283694744 forever2023 D Sept. 30, 2024, 2:53 a.m. OK C++17 (GCC 7-32) TESTS 32 125 16281600
283693974 kbzcz D Sept. 30, 2024, 2:43 a.m. OK C++17 (GCC 7-32) TESTS 32 140 819200
283696417 ihavebigdick D Sept. 30, 2024, 3:16 a.m. OK C++17 (GCC 7-32) TESTS 32 155 27340800
283666808 El-Ged_Sevawy D Sept. 29, 2024, 7:12 p.m. OK C++17 (GCC 7-32) TESTS 30 156 7372800
283670861 Amgad_ktaya D Sept. 29, 2024, 7:46 p.m. OK C++17 (GCC 7-32) TESTS 30 156 11264000
283677514 dalgu D Sept. 29, 2024, 9:02 p.m. OK C++17 (GCC 7-32) TESTS 32 171 819200
283661831 EyadBT D Sept. 29, 2024, 6:44 p.m. OK C++17 (GCC 7-32) TESTS 30 171 6451200
283661771 Pankaj777 D Sept. 29, 2024, 6:44 p.m. OK C++17 (GCC 7-32) TESTS 30 171 6451200
283706483 podys D Sept. 30, 2024, 5:20 a.m. OK C++17 (GCC 7-32) TESTS 33 171 12288000
283688919 OneSheeep D Sept. 30, 2024, 1:15 a.m. OK C++17 (GCC 7-32) TESTS 32 171 27340800
283693931 hyxawa D Sept. 30, 2024, 2:42 a.m. OK C++20 (GCC 13-64) TESTS 32 108 12902400
283703868 mmilesask D Sept. 30, 2024, 4:51 a.m. OK C++20 (GCC 13-64) TESTS 33 124 9728000
283696404 _LSA_ D Sept. 30, 2024, 3:16 a.m. OK C++20 (GCC 13-64) TESTS 32 124 20275200
283686371 ji_114514 D Sept. 30, 2024, 12:15 a.m. OK C++20 (GCC 13-64) TESTS 32 140 5427200
283661495 ademby D Sept. 29, 2024, 6:43 p.m. OK C++20 (GCC 13-64) TESTS 30 140 9011200
283695453 Fluoresce D Sept. 30, 2024, 3:03 a.m. OK C++20 (GCC 13-64) TESTS 32 140 9728000
283704740 VitalyKo D Sept. 30, 2024, 5:01 a.m. OK C++20 (GCC 13-64) TESTS 33 140 10444800
283697484 zfasion D Sept. 30, 2024, 3:31 a.m. OK C++20 (GCC 13-64) TESTS 32 140 15667200
283661123 Re_Sircle D Sept. 29, 2024, 6:42 p.m. OK C++20 (GCC 13-64) TESTS 30 140 16384000
283696811 ThegodbridgeXD D Sept. 30, 2024, 3:21 a.m. OK C++20 (GCC 13-64) TESTS 32 140 19763200
283693010 fishcathu. D Sept. 30, 2024, 2:28 a.m. OK C++23 (GCC 14-64, msys2) TESTS 32 155 9728000
283706067 whale_086 D Sept. 30, 2024, 5:15 a.m. OK C++23 (GCC 14-64, msys2) TESTS 33 155 11059200
283702360 xunoy7 D Sept. 30, 2024, 4:34 a.m. OK C++23 (GCC 14-64, msys2) TESTS 33 156 11673600
283661783 EyadBT D Sept. 29, 2024, 6:44 p.m. OK C++23 (GCC 14-64, msys2) TESTS 30 171 6553600
283661732 EyadBT D Sept. 29, 2024, 6:44 p.m. OK C++23 (GCC 14-64, msys2) TESTS 30 171 6553600
283673541 maybeAayan D Sept. 29, 2024, 8:13 p.m. OK C++23 (GCC 14-64, msys2) TESTS 31 171 7270400
283707352 0x0002 D Sept. 30, 2024, 5:29 a.m. OK C++23 (GCC 14-64, msys2) TESTS 33 171 12800000
283661557 Monir D Sept. 29, 2024, 6:43 p.m. OK C++23 (GCC 14-64, msys2) TESTS 30 171 15667200
283661998 Niloy_Das_19 D Sept. 29, 2024, 6:45 p.m. OK C++23 (GCC 14-64, msys2) TESTS 30 171 17408000
283692058 BananaWolf D Sept. 30, 2024, 2:12 a.m. OK C++23 (GCC 14-64, msys2) TESTS 32 171 23859200
283681775 PlayDate D Sept. 29, 2024, 10:14 p.m. OK Java 21 TESTS 32 421 7270400
283701357 ccj123 D Sept. 30, 2024, 4:22 a.m. OK Java 21 TESTS 33 468 46489600
283710263 AKhacks D Sept. 30, 2024, 5:56 a.m. OK Java 21 TESTS 33 546 23142400
283664437 mohit458 D Sept. 29, 2024, 6:57 p.m. OK Java 21 TESTS 30 608 11673600
283707927 songminsang D Sept. 30, 2024, 5:34 a.m. OK Java 21 TESTS 33 796 27852800
283707748 songminsang D Sept. 30, 2024, 5:33 a.m. OK Java 21 TESTS 33 827 28979200
283680954 PlayDate D Sept. 29, 2024, 9:56 p.m. OK Java 21 TESTS 32 1640 210022400
283680845 PlayDate D Sept. 29, 2024, 9:54 p.m. OK Java 21 TESTS 32 1859 153497600
283662493 NerfThis D Sept. 29, 2024, 6:47 p.m. OK Java 8 TESTS 30 296 5017600
283663149 bnmanubharadwaj D Sept. 29, 2024, 6:50 p.m. OK Node.js TESTS 30 249 32870400
283679590 CLown1331 D Sept. 29, 2024, 9:33 p.m. OK PyPy 3-64 TESTS 32 342 41984000
283656906 CLown1331 D Sept. 29, 2024, 5:34 p.m. OK PyPy 3-64 TESTS 30 405 41984000
283656136 sahibnanda D Sept. 29, 2024, 5:34 p.m. OK PyPy 3-64 TESTS 30 514 67993600
283673774 letsgetgood D Sept. 29, 2024, 8:16 p.m. OK PyPy 3-64 TESTS 31 640 82636800
283664294 letsgetgood D Sept. 29, 2024, 6:56 p.m. OK PyPy 3-64 TESTS 30 749 94515200
283663880 titia D Sept. 29, 2024, 6:54 p.m. OK PyPy 3-64 TESTS 30 764 30515200
283689296 smilences D Sept. 30, 2024, 1:22 a.m. OK PyPy 3-64 TESTS 32 796 25702400
283680854 __baozii__ D Sept. 29, 2024, 9:54 p.m. OK PyPy 3-64 TESTS 32 796 47718400
283672768 ossau_guildo D Sept. 29, 2024, 8:05 p.m. OK PyPy 3-64 TESTS 31 811 67584000
283663940 titia D Sept. 29, 2024, 6:54 p.m. OK PyPy 3-64 TESTS 30 874 31744000
283709346 qasxcvgwe D Sept. 30, 2024, 5:48 a.m. OK Python 3 TESTS 33 1577 71782400
283701551 Spheniscine D Sept. 30, 2024, 4:24 a.m. OK Rust 2021 TESTS 33 406 44544000

remove filters

Back to search problems