fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. const int MAX = 30;
  6.  
  7. int main() {
  8. #ifdef wxh010910
  9.   freopen("input.txt", "r", stdin);
  10. #endif
  11.   int n, m, q;
  12.   scanf("%d %d %d", &n, &m, &q);
  13.   vector<vector<pair<int, int>>> edges(MAX);
  14.   while (q--) {
  15.     int from, to, cost;
  16.     scanf("%d %d %d", &from, &to, &cost);
  17.     --from;
  18.     --to;
  19.     for (int i = cost; i < MAX; ++i) {
  20.       edges[i].emplace_back(from, to);
  21.     }
  22.   }
  23.   vector<long long> answer(m);
  24.   for (int w = 0; w < MAX; ++w) {
  25.     vector<int> p(n << 1);
  26.     vector<long long> tag(m);
  27.     for (int i = 0; i < n << 1; ++i) {
  28.       p[i] = i;
  29.     }
  30.     auto find = [&](int x) {
  31.       while (x != p[x]) {
  32.         x = p[x] = p[p[x]];
  33.       }
  34.       return x;
  35.     };
  36.     vector<pair<int, int>> useful;
  37.     for (auto e : edges[w]) {
  38.       int x = find(e.first), y = find(e.second + n);
  39.       if (x == y) {
  40.         continue;
  41.       }
  42.       if (x > y) {
  43.         swap(x, y);
  44.       }
  45.       p[x] = y;
  46.       ++tag[0];
  47.       if (x >= n && y >= n) {
  48.         useful.emplace_back(x - n, y - n);
  49.       }
  50.     }
  51.     for (int i = 1; i < m && !useful.empty(); ++i) {
  52.       vector<pair<int, int>> new_useful;
  53.       for (auto e : useful) {
  54.         int x = find(e.first), y = find(e.second);
  55.         if (x == y) {
  56.           --tag[i];
  57.         } else {
  58.           if (x > y) {
  59.             swap(x, y);
  60.           }
  61.           p[x] = y;
  62.           if (x >= n && y >= n) {
  63.             new_useful.emplace_back(x - n, y - n);
  64.           }
  65.         }
  66.       }
  67.       swap(useful, new_useful);
  68.     }
  69.     for (int i = 1; i < m; ++i) {
  70.       tag[i] += tag[i - 1];
  71.     }
  72.     for (int i = 1; i < m; ++i) {
  73.       tag[i] += tag[i - 1];
  74.     }
  75.     for (int i = 0; i < m; ++i) {
  76.       answer[i] += (long long)n * (i + 2) - 1 - tag[i];
  77.     }
  78.   }
  79.   for (int i = 0; i < m; ++i) {
  80.     printf("%lld\n", answer[i]);
  81.   }
  82.   return 0;
  83. }
  84.  
Runtime error #stdin #stdout #stderr 2.27s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::bad_alloc'
  what():  std::bad_alloc
https://ideone.com/w5FNL3
language:
C++14 (gcc 8.3)
created:
5 years 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!