fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. // DSU with parity tracking
  5. struct ParityDSU {
  6.     vector<int> p;    // parent
  7.     vector<int> rk;   // rank
  8.     vector<int> xr;   // xor to parent
  9.  
  10.     ParityDSU(int sz = 0) {
  11.         init(sz);
  12.     }
  13.  
  14.     void init(int sz) {
  15.         p.resize(sz);
  16.         rk.assign(sz, 0);
  17.         xr.assign(sz, 0);
  18.         iota(p.begin(), p.end(), 0);
  19.     }
  20.  
  21.     // Returns {root, xor_value}
  22.     pair<int, int> find(int u) {
  23.         if (p[u] == u) {
  24.             return {u, 0};
  25.         }
  26.  
  27.         auto [rt, x] = find(p[u]);
  28.         xr[u] ^= x;
  29.         p[u] = rt;
  30.  
  31.         return {p[u], xr[u]};
  32.     }
  33.  
  34.     // Add constraint: a XOR b = val
  35.     bool add(int a, int b, int val) {
  36.         auto [ra, xa] = find(a);
  37.         auto [rb, xb] = find(b);
  38.  
  39.         // Same set - check if consistent
  40.         if (ra == rb) {
  41.             return (xa ^ xb) == val;
  42.         }
  43.  
  44.         // Union by rank
  45.         if (rk[ra] < rk[rb]) {
  46.             swap(ra, rb);
  47.             swap(xa, xb);
  48.         }
  49.  
  50.         p[rb] = ra;
  51.         xr[rb] = xa ^ xb ^ val;
  52.  
  53.         if (rk[ra] == rk[rb]) {
  54.             rk[ra]++;
  55.         }
  56.  
  57.         return true;
  58.     }
  59. };
  60.  
  61. class Solution {
  62. public:
  63.     // Check if parity queries are consistent
  64.     bool check(long long n, vector<array<long long, 3>>& qs) {
  65.         // Collect all points
  66.         vector<long long> pts;
  67.         pts.push_back(0);
  68.  
  69.         for (auto& q : qs) {
  70.             pts.push_back(q[0]);
  71.             pts.push_back(q[1] + 1);
  72.         }
  73.  
  74.         // Compress coordinates
  75.         sort(pts.begin(), pts.end());
  76.         pts.erase(unique(pts.begin(), pts.end()), pts.end());
  77.  
  78.         auto get = [&](long long v) {
  79.             return (int)(lower_bound(pts.begin(), pts.end(), v) - pts.begin());
  80.         };
  81.  
  82.         ParityDSU dsu(pts.size());
  83.  
  84.         // Process queries
  85.         for (auto& q : qs) {
  86.             int l = get(q[0]);
  87.             int r = get(q[1] + 1);
  88.             int v = (int)q[2];
  89.  
  90.             if (!dsu.add(l, r, v)) {
  91.                 return false;
  92.             }
  93.         }
  94.  
  95.         return true;
  96.     }
  97. };
  98.  
  99. int main() {
  100.     ios::sync_with_stdio(false);
  101.     cin.tie(nullptr);
  102.  
  103.     long long n;
  104.     int m;
  105.     cin >> n >> m;
  106.  
  107.     vector<array<long long, 3>> qs(m);
  108.     for (int i = 0; i < m; i++) {
  109.         cin >> qs[i][0] >> qs[i][1] >> qs[i][2];
  110.     }
  111.  
  112.     Solution sol;
  113.     bool ans = sol.check(n, qs);
  114.  
  115.     cout << (ans ? "YES" : "NO") << "\n";
  116.  
  117.     return 0;
  118. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/g3sEkf
language:
C++14 (gcc 8.3)
created:
4 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!