Codeforces Round #263 Div. 1 Problem D - 2 SAT problem

Problem Statement:
461D - Appleman and Complicated Task

Solution:
I took a few days to solve this haha. The idea is already explained pretty clearly in the official tutorial:
1. Consider cell(i,j). This cell is in the neighbourhood of cell(i-1, j), hence it must fulfil the requirement: cell(i-1,j-1) XOR cell(i-1, j+1) XOR cell(i-1, j-2) XOR cell(i,j) = 0   (so that the number of cell with 'o' is even). This means that cell(i,j) can be totally determinable from those corresponding cells.
2. From 1, we can prove by induction that if the first row of the table is known, then we can fully determine the rest of the rows using the above relationship.
3. Another key observation: cell(i,j) is determined by a sequence of consecutive odd or even-indexed elements of the top row. To see this, you need to draw out the relationship and find the pattern.

4. From there, you can determine the range of values (L, R) of the top elements that will affect cell(i,j). From here, we get a system of equations in the form of \(a_L \oplus a_{L+2} \oplus a_{L+4} \oplus \ldots \oplus a_R = k\), where k is the content of cell(i,j). Since they are consecutive odd-index/even-indexed, we can represent them more conveniently in term of sum of prefixes \((a_L \oplus \ldots \oplus a_{E}) \oplus ( a_{R+2} \oplus  \ldots \oplus a_{E}) = k\) where E indicates the end of the prefix sum.
5. Finally from here we need to compute the number of independent equations out of the \(K\) equations. Each set of interlinked equations will give us two choices of assigning the variables. However if any of the variables have been preassigned, we only have 1 choice of assigning the rest of the variables in that set of dependent equations.
6. Don't forget to check for consistency. By far this is the most difficult task. One of the way is to use DFS to check for congruency in the assignment, using a method similar to flood fill/bipartite coloring.

Implementation:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#include <utility>
#include <map>
#include <cstring>
using namespace std;

int N, E;
vector<pair<int,int> > eqn;
vector<int> val;
vector<vector<pair<int,int> > > adj;
int col[100005];
int f[100005];
bool inconsistent;

void dfs(int u, int r) {
 if(inconsistent) return;
 if(col[u] != -1) {
  if(col[u] != r) {
   inconsistent = true;
  }
  return;
 } else {
  col[u] = r;
  for(int i=0;i<adj[u].size();++i) {
   int v = adj[u][i].first;
   int m = adj[u][i].second;
   dfs(v, r^m);
   if(inconsistent) return;
  }
 }
}

void solve() {
 scanf("%d %d", &N, &E);
 int u,v,k;
 char ch;
 for(int i=0;i<E;++i){
  scanf("%d %d %c", &u, &v, &ch);
  eqn.push_back(make_pair(u-1,v-1));
  if(ch == 'o') val.push_back(1);
  else val.push_back(0);
 }
 adj = vector<vector<pair<int,int> > >(N+3);
 int L, R;
 int even, odd;
 if(N%2 == 0) {
  even = N;
  odd = N+1;
 } else {
  odd = N+1;
  even = N;
 }
 for(int i = 0; i < E; ++i) {
  u = eqn[i].first;
  v = eqn[i].second;
  k = val[i];
  L = (u-v > 0 ? u-v : v-u);
  R = (0 > u+v - N ? u+v : 2*(N-1) - (u+v));
  if(R+2 == ((u+v)%2 == 0 ? even:odd)) {
   adj[L].push_back(make_pair(R+2,k));
   continue;
  }
  adj[L].push_back(make_pair(R+2,k));
  adj[R+2].push_back(make_pair(L,k));
 }
 long long ans = 1;
 int diff = 0;
 memset(col, -1, sizeof(col));
 inconsistent = false;
 for(int i=0;i<N;++i) {
  if(inconsistent) break;
  if(col[i] == -1) {
   col[even] = col[odd] = -1;
   dfs(i,0);
   if(col[even] == -1 && col[odd] == -1) ++diff;
  }
 }
 if(inconsistent) {
  printf("0\n");
  return;
 }
 for(int i=0;i<diff;++i) {
  ans = (ans * 2) % (1000000007);
 }
 cout << ans << endl;
}

int main() {
 solve();
 return 0;
}