optimum cpp solution : Connect the Dots time limit per test2 seconds memory limit per…
- User
optimum cpp solution : Connect the Dots time limit per test2 seconds memory limit per test512 megabytes 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 ai , di (1≤di≤10 ), and ki . She selects points ai,ai+di,ai+2di,ai+3di,…,ai+ki⋅di and connects each pair of these points with arcs. After performing all m operations, she wants to know the number of connected components† these points form. Please help her find this number.
† 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.
Input Each test contains multiple test cases. The first line contains the number of test cases t (1≤t≤105 ). The description of the test cases follows.
The first line of each test case contains two integers n and m (1≤n≤2⋅105 , 1≤m≤2⋅105 ).
The i -th of the following m lines contains three integers ai , di , and ki (1≤ai≤ai+ki⋅di≤n , 1≤di≤10 , 0≤ki≤n ).
It is guaranteed that both the sum of n and the sum of m over all test cases do not exceed 2⋅105 .
Output For each test case, output the number of connected components.
Example InputCopy 3 10 2 1 2 4 2 2 4 100 1 19 2 4 100 3 1 2 5 7 2 6 17 2 31 OutputCopy 2 96 61 Note 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 points 19 , 21 , 23 , 25 , and 27 . Now all of them form a single connected component of size 5 . The other 95 points form single-point connected components. Thus, the answer is 1+95=96 .
In the third test case, there are n=100 points. After the operations, all odd points from 1 to 79 will be in one connected component of size 40 . The other 60 points form single-point connected components. Thus, the answer is 1+60=61 .
- Assistant
To solve the "Connect the Dots" problem, we can use the Disjoint Set Union (DSU) or Union-Find data structure. The DSU is very effective for handling dynamic connectivity queries, which is exactly what the problem requires when connecting the dots.
Problem Breakdown:
-
Description: We have multiple test cases where each test case consists of points along a line and a series of operations that connect certain points based on arithmetic sequences. After performing all operations, the goal is to determine the number of connected components.
-
Constraints:
- The number of test cases ( t ) can be as large as ( 10^5 ).
- For each test case, ( n ) (number of points) and ( m ) (number of operations) can also be large, but the sum of all ( n ) across all test cases is limited to ( 2 \times 10^5 ), and the same limit applies to ( m ).
Approach:
-
DSU Initialization: For each test case, initialize a DSU where each point initially is its own parent (i.e., each point is its own connected component).
-
Processing Operations:
- For each operation, connect all points in the specified arithmetic sequence.
- The sequence is determined by ( ai, ai+di, ai+2di, \ldots, ai+ki \times di ).
- Use the DSU
unionoperation to connect these points efficiently.
-
Counting Connected Components:
- After all operations, we determine the number of unique roots in the DSU, which corresponds to the number of connected components.
- Utilize path compression in the DSU to optimize the find operations.
-
Efficiency:
- Given the large input size, efficient I/O operations are crucial.
- The use of path compression and union by rank ensures that each operation is nearly constant time.
Implementation:
The solution is implemented in C++ with careful attention to efficiency, especially in handling the DSU operations and the input/output operations.
#include <bits/stdc++.h> using namespace std; // Fast IO struct FastIO { FastIO() { ios::sync_with_stdio(false); cin.tie(NULL); } }; // Global variables for counting unique roots const int MAXN = 200001; int stamp_arr[MAXN]; int current_stamp = 1; int main(){ FastIO fio; int t; cin >> t; while(t--){ int n, m; cin >> n >> m; // Initialize parent and rank arrays vector<int> parent(n+1); vector<int> rank_arr(n+1, 1); for(int i=1;i<=n;i++) parent[i] = i; // Define find_set with path compression auto find_set = [&](auto &find_set_ref, int x) -> int { while(x != parent[x]){ parent[x] = parent[parent[x]]; x = parent[x]; } return x; }; // Process m operations for(int op=0; op<m; op++){ int ai, di, ki; cin >> ai >> di >> ki; if(ki >=1){ int first = ai; for(int j=1; j<=ki; j++){ int current = ai + j * di; if(current > n) break; // Just in case, though constraints say ai + ki*di <=n // Union first and current int pa = find_set(find_set, first); int pb = find_set(find_set, current); if(pa != pb){ if(rank_arr[pa] < rank_arr[pb]){ parent[pa] = pb; } else{ parent[pb] = pa; if(rank_arr[pa] == rank_arr[pb]){ rank_arr[pa]++; } } } } } } // Count unique roots int count =0; for(int i=1; i<=n; i++){ int root = find_set(find_set, i); if(stamp_arr[root] != current_stamp){ stamp_arr[root] = current_stamp; count++; } } current_stamp++; cout << count << "\n"; } }Explanation:
-
Initialization:
- We initialize the DSU with each point being its own parent and set their ranks to 1.
-
Finding the Root:
- The
find_setlambda function locates the root of a given point with path compression to flatten the structure for efficiency.
- The
-
Union Operation:
- For each operation, if ( ki \geq 1 ), we connect all points in the arithmetic sequence by uniting them with the first point in the sequence.
- The union by rank strategy ensures that the tree remains balanced, keeping operations efficient.
-
Counting Components:
- After all operations, we iterate through each point, find its root, and use a stamping mechanism to count unique roots, representing the connected components.
-
Output:
- We print the number of connected components for each test case.
This approach ensures that the solution runs efficiently within the given constraints.
-