fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define int long long
  6. #define _3bkarm cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
  7.  
  8.  
  9. struct dsu {
  10.     int number_of_components;
  11.     vector<int> parent, size;
  12.  
  13.     void build(int n) {
  14.         number_of_components = n - 1;
  15.         size.assign(n, 1);
  16.         parent.assign(n, 0);
  17.         for (int i = 0; i < n; ++i) {
  18.             parent[i] = i;
  19.         }
  20.     }
  21.  
  22.     int root(int u) {
  23.         while (u != parent[u]) {
  24.             u = parent[u] = parent[parent[u]];
  25.         } return u;
  26.     }
  27.  
  28.     int is_same_set(int u, int v) {
  29.         return root(u) == root(v);
  30.     }
  31.  
  32.     void merge(int u, int v) {
  33.         int u_root = root(u);
  34.         int v_root = root(v);
  35.  
  36.         if (u_root == v_root) {
  37.             return;
  38.         }
  39.  
  40.         if (size[u_root] < size[v_root]) {
  41.             swap(u_root, v_root);
  42.         }
  43.  
  44.         --number_of_components;
  45.         size[u_root] += size[v_root];
  46.         parent[v_root] = u_root;
  47.     }
  48. };
  49.  
  50. void get_shit_done() {
  51.     int n, m;
  52.     cin >> n >> m;
  53.  
  54.     set<int> adj[11][10];
  55.     for (int i = 1; i <= n; ++i) {
  56.         for (int j = 1; j <= 10; ++j) {
  57.             adj[j][i % j].insert(i);
  58.         }
  59.     }
  60.  
  61.     dsu ds;
  62.     ds.build(n + 1);
  63.     for (int i = 0, a, d, k; i < m; ++i) {
  64.         cin >> a >> d >> k;
  65.         int x = d;
  66.         int y = a % d;
  67.         int lim = a + k * d;
  68.  
  69.         vector<int> del;
  70.         adj[x][y].erase(a);
  71.         auto it = adj[x][y].lower_bound(a);
  72.  
  73.         int lst = a + d;
  74.         while ( it != adj[x][y].end() and *it <= lim ) {
  75.             ds.merge(a, lst);
  76.             ds.merge(a, *it);
  77.             del.push_back(*it);
  78.             lst = *it + d;
  79.             ++it;
  80.         }
  81.         if (lst <= lim) {
  82.             ds.merge(a, lst);
  83.         }
  84.  
  85.         for (int id : del) {
  86.             adj[x][y].erase(id);
  87.         }
  88.     }
  89.  
  90.     cout << ds.number_of_components << '\n';
  91. }
  92.  
  93. signed main() {
  94.     _3bkarm
  95.  
  96.     int ts = 1;
  97.     cin >> ts;
  98.     while (ts--) {
  99.         get_shit_done();
  100.     }
  101.  
  102.     return 0;
  103. }
Success #stdin #stdout 0.01s 5272KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/DpikqO
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!