fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define eb emplace_back
  5. #define pii pair <int, int>
  6. #define fi first
  7. #define se second
  8. #define all(ac) ac.begin(), ac.end()
  9. #define MASK(x) (1 << x)
  10. #define ub(i, j) ((i >> j) & 1)
  11.  
  12. const int MOD = 1e9 + 9999;
  13. int mul(int x, int y) {
  14.     return 1LL * x * y % MOD;
  15. }
  16.  
  17. struct DSU {
  18.     int n;
  19.     vector <int> lab;
  20.  
  21.     DSU(int n): n(n), lab(n + 1, -1) {}
  22.  
  23.     int find(int u) {return lab[u] < 0 ? u : lab[u] = find(lab[u]);}
  24.  
  25.     bool join(int u, int v) {
  26.         u = find(u);
  27.         v = find(v);
  28.  
  29.         if(u != v) {
  30.             if(lab[u] > lab[v]) swap(u, v);
  31.             lab[u] += lab[v];
  32.             lab[v] = u;
  33.             return 1;
  34.         }
  35.         return 0;
  36.     }
  37. };
  38.  
  39. int n, m, T;
  40.  
  41. struct Data {
  42.     int x, y, w;
  43.     Data(int x, int y, int w): x(x), y(y), w(w) {}
  44. };
  45.  
  46. vector <Data> vt;
  47. map <pii, int> mp;
  48.  
  49. bool ident() {
  50.     vector <int> rv;
  51.     for(Data &e : vt) {
  52.         rv.eb(e.x);
  53.         rv.eb(e.y);
  54.     }
  55.  
  56.     sort(all(rv));
  57.     rv.erase(unique(all(rv)), rv.end());
  58.  
  59.     for(Data &e : vt) {
  60.         e.x = lower_bound(all(rv), e.x) - rv.begin() + 1;
  61.         e.y = lower_bound(all(rv), e.y) - rv.begin() + 1;
  62.     }
  63.  
  64.     vector <pii> zero, one;
  65.     for(Data &e : vt) {
  66.         if(e.w) one.eb(make_pair(e.x, e.y));
  67.         else zero.eb(make_pair(e.x, e.y));
  68.     }
  69.  
  70.     DSU dsu((int) rv.size());
  71.     int last[(int) rv.size() + 1];
  72.     memset(last, 0, sizeof last);
  73.     for(pii &pos : zero) {
  74.         if(last[pos.fi])
  75.             dsu.join(pos.se, last[pos.fi]);
  76.         last[pos.fi] = pos.se;
  77.     }
  78.  
  79.     memset(last, 0, sizeof last);
  80.     for(pii &pos : one) {
  81.         if(last[pos.fi])
  82.             dsu.join(last[pos.fi], pos.se);
  83.         last[pos.fi] = pos.se;
  84.     }
  85.  
  86.     vector <pii> G[(int) rv.size() + 1];
  87.  
  88.  
  89.     for(pii &pos : zero) {
  90.         G[dsu.find(pos.se)].eb(pos.fi, 0);
  91.     }
  92.  
  93.     for(pii &pos : one) {
  94.         G[dsu.find(pos.se)].eb(pos.fi, 1);
  95.     }
  96.  
  97.     for(int i=1;i<= (int) rv.size();i++) {
  98.         sort(all(G[i]));
  99.         int col = -1, color = -1;
  100.         for(pii &v : G[i]) {
  101.             if(col != v.fi) {
  102.                 col = v.fi;
  103.                 color = v.se;
  104.             }
  105.             else
  106.             if(color != v.se) return 0;
  107.         }
  108.     }
  109.     return 1;
  110. }
  111.  
  112. int Pow(int a, int b) {
  113.     int res = 1;
  114.     while(b > 0) {
  115.         if(b & 1) res = mul(res, a);
  116.         a = mul(a, a), b >>= 1;
  117.     }
  118.     return res;
  119. }
  120.  
  121. int32_t main() {
  122.     ios::sync_with_stdio(false);
  123.     cin.tie(0), cout.tie(0);
  124.     #define task "tet"
  125.     if(fopen(task".inp", "r")) {
  126.         freopen(task".inp", "r", stdin);
  127.         freopen(task".out", "w", stdout);
  128.     }
  129.  
  130.     cin >> n >> m >> T;
  131.  
  132.     for(int i=1;i<=T;i++) {
  133.         int x, y, w; cin >> x >> y >> w;
  134.         pii cur = make_pair(x, y);
  135.         if(mp[cur]) {
  136.             if(mp[cur] != w + 1) return cout << 0, 0;
  137.         }
  138.         else {
  139.             mp[cur] = w + 1;
  140.             vt.eb(x, y, w);
  141.         }
  142.     }
  143.  
  144.     T = (int) vt.size();
  145.  
  146.     if(!ident()) cout << 0;
  147.     else cout << Pow(2, n + m - T - 1);
  148.     return 0;
  149. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
2 2 2
1 1 0
2 2 0
stdout
copy 
2
https://ideone.com/vvScgG
language:
C++14 (gcc 8.3)
created:
9 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!