Tags: c++ xor graphs
Rating:
Let's assume aur keys are in array A[1..N], where N = 10^5.
For simplicity, A[0] = 0
Now assume a prefix-xor array of A, P[0..N], such that P[i] = XOR(A[0..i])
Now, the given tests (L, R, V) imply only one condition, P[R] xor P[L-1] == V
Note that XOR(A[L..R]) = P[R] xor P[L-1]
Now, build a graph with N+1 vertices (from 0 to N), and for each test, add edge from (L-1 <-> R) with value V .
Now for each "connected component" in this graph, set P[node] = 0 (or number) for any one node, and run a dfs from that node setting the neighbor node as its value xor weight of edge.
Finally you have array P[0..N], now reduce it A[1..N] by A[i] = P[i] xor P[i-1]
```cpp
#define SZ(v) int((v).size())
int main() {
cin.tie(nullptr) -> sync_with_stdio(false);
const int n = (int) 1e5;
vector<int> l(n), r(n), v(n);
vector<vector<pair<int, int>>> g(n + 1);
for (int i = 0; i < n; ++i) {
cin >> l[i] >> r[i] >> v[i];
g[l[i] - 1].push_back({r[i], v[i]});
g[r[i]].push_back({l[i] - 1, v[i]});
}
error("donereading");
vector<int> ans(n + 1, -1);
for (int s = 0; s <= n; ++s) if (ans[s] == -1) {
ans[s] = 0;
vector<int> bfs = {s};
for (int i = 0; i < SZ(bfs); ++i) {
int u = bfs[i];
for (auto [w, x] : g[u]) {
if (~ans[w]) assert (ans[w] == (x ^ ans[u]));
else ans[w] = x ^ ans[u], bfs.push_back(w);
}
}
}
for (int i = n; i > 0; --i) {
ans[i] ^= ans[i - 1];
}
error("doneprocessing");
for (int i = 1; i <= n; ++i) {
cout << ans[i] << endl;
}
error("donewriting");
string flag;
cin >> flag;
error(flag);
}
```
```bash
mkfifo p1
mkfifo p2
./a.out < p1 > p2 &
nc 2020.redpwnc.tf 31458 > p1 < p2 &
```
