http://codeforces.me/contest/1074/submission/45462396
http://codeforces.me/contest/1074/submission/45462405
These two codes are exactly the same, except for this part:
In the Wrong answer on test 14 submission:
for (int i : inTree[rootp]) {
inTree[rootq].pb(i);
distToRoot[i] = distToRoot[i] ^ distToRoot[p] ^ edgeWeight ^ distToRoot[q];
root[i] = rootq;
}
In the Accepted submission:
edgeWeight ^= distToRoot[p] ^ distToRoot[q];
for (int i : inTree[rootp]) {
inTree[rootq].pb(i);
distToRoot[i] ^= edgeWeight;
root[i] = rootq;
}
(This is the end of the method, so xor-equals edgeWeight shouldn't change anything later on.)
I thought xor sum is both commutative and associative? What's the difference between these two snippets? Am I missing something really obvious? Thanks in advance.
Not my bug, xor's bug
The for loop also modifies the values of distToRoot[p] and distToRoot[q] hence the WA.In your second submission, the original values of distToRoot[p] and distToRoot[q] are used to update other indices. There is no problem with xor here.
Wow, can't believe I missed that. Thanks!
The xor summing rule is simple:
and 
. In the Accepted submission, the logic value xor summed with
distToRoot[i]in each iteration is computed before the loop. Therefore, the logic value ofdistToRoot[p] ^ edgeWeight ^ distToRoot[q]is invariant to the iteration variablei, i.e. does not change inside the loop. In the Wrong Answer submission, when the number of negation operations made todistToRoot[p]anddistToRoot[q]in previous iterations of the loop is an odd number, the logic value xor summed withdistToRoot[i]is the complement ofedgeWeightin the AC code.