fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. #define MASK(x) (1LL << (x))
  6. #define BIT(x, i) (((x) >> (i)) & 1)
  7. #define ALL(x) (x).begin(), (x).end()
  8.  
  9. #define REP(i, n) for (int i = 0, _n = n; i < _n; ++i)
  10. #define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
  11. #define FORD(i, a, b) for (int i = (a), _b = (b); i >= _b; --i)
  12. #define FORE(it, s) for (__typeof(s.begin()) it = (s).begin(); it != (s).end(); ++it)
  13.  
  14. #define TIME (1.0 * clock() / CLOCKS_PER_SEC)
  15. #define file(TASK)                         \
  16.     if (fopen(TASK ".inp", "r")) {         \
  17.         freopen(TASK ".inp", "r", stdin);  \
  18.         freopen(TASK ".out", "w", stdout); \
  19.     }
  20.  
  21. template <class U, class V> bool maximize(U &A, const V &B) { return (A < B) ? (A = B, true) : false; }
  22. template <class U, class V> bool minimize(U &A, const V &B) { return (A > B) ? (A = B, true) : false; }
  23. const int Mod = 1e9 + 7;
  24. const int MAXN = 1e5 + 5;
  25. struct QUERY {
  26.     int l, r, value;
  27. }queries[MAXN];
  28. int N, Q, color[MAXN];
  29. vector <int> same_color[MAXN], diff_color[MAXN];
  30. int ans = 1;
  31. void dfs(int u, int tmpColor) {
  32.     if(color[u] != -1 && color[u] != tmpColor) {
  33.         cout << 0;
  34.         exit(0);
  35.     }
  36.     if(color[u] != -1) return;
  37.     color[u] = tmpColor;
  38.     for (auto v : same_color[u]) dfs(v, tmpColor);
  39.     for (auto v : diff_color[u]) dfs(v, 1 ^ tmpColor);
  40. }
  41. int calc(int biti) {
  42.     fill(same_color, same_color + N + 1, vector <int> ());
  43.     fill(diff_color, diff_color + N + 1, vector <int> ());
  44.     fill(color, color + N + 1, -1);
  45.     FOR(i, 1, Q) {
  46.         if(BIT(queries[i].value, biti)) {
  47.             diff_color[queries[i].l - 1].push_back(queries[i].r);
  48.             diff_color[queries[i].r].push_back(queries[i].l - 1);
  49.         } else {
  50.             same_color[queries[i].l - 1].push_back(queries[i].r);
  51.             same_color[queries[i].r].push_back(queries[i].l - 1);
  52.         }
  53.     }
  54.     int ans = 1;
  55.     REP(u, N + 1) if(color[u] == -1) {
  56.         dfs(u, 0);
  57.         if(u > 0) ans += ans;
  58.         if(ans >= Mod) ans -= Mod;
  59.     }
  60.     return ans;
  61. }
  62. void process(void) {
  63.     cin >> N >> Q;
  64.     FOR(i, 1, Q) cin >> queries[i].l >> queries[i].r >> queries[i].value;
  65.     REP(biti, 30) ans = 1LL * ans * calc(biti) % Mod;
  66.     cout << ans;
  67. }
  68. signed main() {
  69.     file("TASK");
  70.     ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
  71.     int test = 1;
  72.     // cin >> test;
  73.     while(test--) {
  74.         process();
  75.         cout << '\n';
  76.     }
  77.     cerr << "Time elapsed: " << TIME << " s.\n";
  78.     return (0 ^ 0);
  79. }
Success #stdin #stdout #stderr 0.01s 8536KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
stderr
copy 
Time elapsed: 0.005107 s.
https://ideone.com/gPI3os
language:
C++ (gcc 8.3)
created:
8 hours 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!