fork download
copy 
  1. #include <cmath>
  2. #include <cstring>
  3. #include <cstdio>
  4. #include <cstdlib>
  5. #include <iostream>
  6. #include <fstream>
  7. #include <algorithm>
  8.  
  9. #define rep(i, l, r) for(int i = l; i <= r; i++)
  10. #define down(i, l, r) for(int i = l; i >= r; i--)
  11. #define MS 1234
  12. #define MAX 1037471823
  13.  
  14. using namespace std;
  15.  
  16. struct node
  17. {
  18.     int x, y, z;
  19.     bool operator < (const node &k) const { return z < k.z; }
  20. } c[2345];
  21.  
  22. int n, m, h[1234][MS], t[1234], ans, now, a, o, h2[23][MS];
  23. bool b[MS];
  24.  
  25. int Head(int x)
  26. {
  27.     while (h[o][h[o][x]] != h[o][x]) h[o][x] = h[o][h[o][x]];
  28.     return h[o][x];
  29. }
  30.  
  31. int Head2(int x, int o)
  32. {
  33.     while (h2[o][h2[o][x]] != h2[o][x]) h2[o][x] = h2[o][h2[o][x]];
  34.     return h2[o][x];
  35. }
  36.  
  37. void Search(int x, int y, int t, int o)
  38. {
  39.     if (t == 0) { now++; return; }
  40.     rep(i, x, y-t+1) if (Head2(c[i].x, t) != Head2(c[i].y, t)) 
  41.     {
  42.         rep(j, 1, n) h2[t-1][j] = h2[t][j];
  43.         h2[t-1][h2[t-1][c[i].x]] = h2[t-1][c[i].y];
  44.         Search(i+1, y, t-1, o);
  45.     }
  46. }
  47.  
  48. int main()
  49. {
  50.     scanf("%d%d", &n, &m); ans = 1;
  51.     rep(i, 1, m) scanf("%d%d%d", &c[i].x, &c[i].y, &c[i].z);
  52.     rep(i, 1, m) b[c[i].x] = b[c[i].y] = true;
  53.     rep(i, 1, n) if (b[i] == false) { printf("0\n"); return 0; } 
  54.     sort(c+1, c+1+m); c[m+1].z = MAX;
  55.     a = 0; rep(i, 1, m+1) if (c[i].z != c[i-1].z) { rep(j, a+1, i-1) c[j].z = c[a].z+1; a = i-1; }
  56.  
  57.     rep(i, 1, n) h[0][i] = i;
  58.     a = o = 0; rep(i, 1, m)
  59.     {
  60.         if (c[i].z != c[i-1].z)
  61.         {
  62.             rep(j, 1, n) h[o+1][j] = h[o][j]; o++;
  63.         }
  64.         if (Head(c[i].x) != Head(c[i].y)) h[o][h[o][c[i].x]] = h[o][c[i].y], t[o]++;
  65.     }
  66.     a = 1; rep(i, 2, m+1) if (c[i].z != c[i-1].z)
  67.     {
  68.         rep(j, 1, n) h2[t[c[a].z]][j] = h[c[a].z-1][j]; now = 0;
  69.         Search(a, i-1, t[c[a].z], c[a].z-1); 
  70.         a = i; ans = (ans * now) % 31011;
  71.     }
  72.     printf("%d\n", ans);
  73.     return 0;
  74. }
Success #stdin #stdout 0s 9400KB
comments (?)
stdin
copy 
4 6
1 2 1
1 3 1
1 4 1
2 3 2
2 4 1
3 4 1
stdout
copy 
8
https://ideone.com/RFH8gJ
BZOJ 1016
language:
C++ (gcc 8.3)
created:
10 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!