BlackVienna.java

import java.util.*;
import java.util.stream.IntStream;

public class BlackVienna {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		TwoSAT solver = new TwoSAT(2 * 26);
		for (int i = 0; i < N; i++) {
			char cs[] = sc.next().toCharArray();
			int v1 = cs[0] - 'A';
			int v2 = cs[1] - 'A';
			int player = sc.nextInt() - 1;
			int reply = sc.nextInt();
			switch (reply) {
			case 0:
				solver.setFalse(v1 + (player * 26));
				solver.setFalse(v2 + (player * 26));
				break;
			case 1:
				solver.setXor(v1 + (player * 26), v2 + (player * 26));
				break;
			case 2:
				solver.setTrue(v1 + player * 26);
				solver.setTrue(v2 + player * 26);
				break;
			default:
				throw new NullPointerException();
			}
		}
		List<Integer>[] copy = getCopy(solver.adj);
		List<String> combList = new ArrayList<String>(2600);
		char [] susp = new char [] { 'A', 'B', 'C', 'D', 'E', 'F', 'G',
				'H', 'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z'};
		char [] comb = new char[3];
		makecomb(susp,0,0, comb, combList);
		int count = 0;
		for (String combs: combList){
			solver.adj = getCopy(copy);
			char [] suspects = combs.toCharArray();
			for (char c: suspects){
				int v = c - 'A';
				solver.setFalse(v);
				solver.setFalse(v + 26);
			}
			for (char c: susp){
				if (!combs.contains(String.valueOf(c))){
					int v = c - 'A';
					solver.setXor(v,v+26);
				}
			}
			if (solver.isSatisfiable()){
				count++;
			}
		}
		System.out.println(count);

	}

	static class TwoSAT {

		List<Integer>[] adj; // implication graph
		SCC scc;
		int N; // N variables, 2*N nodes to represent var[i] and !var[i]

		@SuppressWarnings("unchecked")
		public TwoSAT(int N) {
			this.N = N;
			adj = new List[2 * N];
			for (int i = 0; i < 2 * N; i++)
				adj[i] = new ArrayList<Integer>();
		}

		/* var1 xor var2 means var1 || var2 && !var || !var2 */
		void setXor(int var1, int var2) {
			addDisjunction(var1, false, var2, false);
			addDisjunction(var1, true, var2, true);
		}

		/*
		 * Record a clause 'var1' || 'var2', optionally var1/var2 negated. Since
		 * x || y == (!x -> y) && (!y -> x), add two implication edges.
		 *
		 * Pass 'negated' to be false if you mean 'var' Pass 'negated' to be
		 * true if you mean '!var'
		 */
		void addDisjunction(int var1, boolean negated1, int var2, boolean negated2) {
			// !var1 -> var2
			adj[!negated1 ? N + var1 : var1].add(!negated2 ? var2 : var2 + N);
			// !var2 -> var1
			adj[!negated2 ? N + var2 : var2].add(!negated1 ? var1 : var1 + N);
		}

		/* Shorthand that can be used instead of setTrue/setFalse, see below */
		void set(int var, boolean value) {
			addDisjunction(var, !value, var, !value);
		}

		/* Setting a variable to true is saying that var || var */
		void setTrue(int var) {
			addDisjunction(var, false, var, false);
		}

		/* Setting a variable to false is saying that !var || !var */
		void setFalse(int var) {
			addDisjunction(var, true, var, true);
		}

		/*
		 * Determine satisfiability: if any x and !x are in the same SCC, the
		 * answer is false - why? Because x -> !x is a contradiction.
		 */
		boolean isSatisfiable() {
			scc = new SCC(adj);
			for (int i = 0; i < N; i++) {
				if (scc.stronglyConnected(i, i + N)) {
					return false;
				}
			}
			return true;
		}

		/*
		 * To-be-done - outputting an actual solution where needed. DFS from
		 * each fixed variable along the implication chain. WF handbook has code
		 * fragment, but was this ever tested (!?).
		 */
	}

	/*************************************************************************
	 *
	 * Compute the strongly-connected components of a digraph using Tarjan's
	 * algorithm. (Original Source: Sedgwick)
	 *
	 * Runs in O(E + V) time. Recursive implementation.
	 */
	static class SCC {

		private boolean[] marked; // marked[v] = has v been visited?
		private int[] id; // id[v] = id of strong component containing v
		private int[] low; // low[v] = low number of v
		private int pre; // preorder number counter
		private int count; // number of strongly-connected components
		private Stack<Integer> stack;
		private int[] sccsize; // size of scc[i], only if desired
		private List<Integer>[] G; // store underlying graph, only needed for
									// reduce

		public SCC(List<Integer>[] G) {
			this.G = G;
			marked = new boolean[G.length];
			stack = new Stack<Integer>();
			id = new int[G.length];
			low = new int[G.length];
			sccsize = new int[G.length];
			for (int v = 0; v < G.length; v++) {
				if (!marked[v])
					dfs(G, v);
			}
		}

		private void dfs(List<Integer>[] G, int v) {
			marked[v] = true;
			low[v] = pre++;
			int min = low[v];
			stack.push(v);
			for (int w : G[v]) {
				if (!marked[w])
					dfs(G, w);
				if (low[w] < min)
					min = low[w];
			}
			if (min < low[v]) {
				low[v] = min;
				return;
			}
			int w;
			do {
				w = stack.pop();
				id[w] = count;
				sccsize[count]++;
				low[w] = G.length;
			} while (w != v);
			count++;
		}

		// return the number of strongly connected components
		public int count() {
			return count;
		}

		// are v and w strongly connected?
		public boolean stronglyConnected(int v, int w) {
			return id[v] == id[w];
		}

		// in which strongly connected component is vertex v?
		public int id(int v) {
			return id[v];
		}

		// how big is the strongly connected component with number #x
		// assert 0 <= x < count
		public int sccsize(int x) {
			return sccsize[x];
		}

		/*
		 * Return reduced acyclic graph in which all SCC are collapsed into one
		 * node
		 */
		@SuppressWarnings("unchecked")
		public List<Integer>[] reduce() {
			Set<Integer>[] set = new Set[count];
			for (int i = 0; i < count; i++)
				set[i] = new HashSet<>();

			for (int i = 0; i < G.length; i++)
				for (Integer j : G[i])
					if (!stronglyConnected(i, j))
						set[id[i]].add(id[j]);

			List<Integer>[] r = new List[count];
			for (int i = 0; i < count; i++)
				r[i] = new ArrayList<>(set[i]);

			return r;
		}
	}

	public static List<Integer>[] getCopy(List<Integer>[] arr) {
		List<Integer> arr2[] = new List[arr.length];
		for (int i = 0; i < arr.length; i++) {
			arr2[i] = new ArrayList<Integer>();
			for (int num : arr[i]) {
				arr2[i].add(num);
			}
		}
		return arr2;
	}

	static void makecomb(char[] a, int pos, int idx, char[] comb, List<String> combList) {
		if (pos == comb.length) {
			combList.add(String.valueOf(comb));
			return;
		}

		for (int i = idx; i < a.length; i++) {
			comb[pos] = a[i];
			makecomb(a, pos + 1, i + 1, comb, combList);
		}
	}

}