CodeChef submission 130804 (JAVA) plaintext list. Status: TLE, problem J6, contest NOV09. By abhinava.srivastava (abhinava.srivastava), 2009-11-11 12:55:14.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
 
public class Main {
	int n; // no of politicians
 
	int k; // no of evidences...
 
	List<String> resultingStateList = new ArrayList<String>();
 
	int[][] evidences;
 
	public static void main(String[] args) throws CloneNotSupportedException,
			NumberFormatException, IOException {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
 
		int noOfTestCases = Integer.parseInt(in.readLine());
 
		testcase: for (int count = 0; count < noOfTestCases; count++) {
			Main main = new Main();
			String str = in.readLine();
			int idx = str.indexOf(' ');
			main.n = Integer.parseInt(str.substring(0, idx));
			main.k = Integer.parseInt(str.substring(idx + 1));
			main.evidences = new int[main.k][2];
			for (int i = 0; i < main.k; i++) {
				StringTokenizer st = new StringTokenizer(in.readLine());
				int x1 = Integer.parseInt(st.nextToken());
				int y1 = Integer.parseInt(st.nextToken());
				main.evidences[i][0] = x1;
				main.evidences[i][1] = y1;
 
			}
			if (count != noOfTestCases - 1)
				in.readLine();
 
			Queue<State> Q = new LinkedList<State>();
 
			String politiciansStatus = new String("");
			for (int p = 0; p < main.n; p++)
				politiciansStatus += "*";
 
			if (main.n > 0 && main.k == 0) {
				out.println("MULTIPLE");
				continue;
			}
			if (main.n == 0) {
				out.println("UNIQUE");
				continue;
			}
			Q.add(new State(0, politiciansStatus));
			while (!Q.isEmpty()) {
				State s = Q.remove();
				List<State> processesdList = main.process(s);
 
				if (!(processesdList.size() == 1 && processesdList.get(0)
						.equals(State.SENTINEL_STATE))) {
					for (State a : processesdList) {
						if (a.noOfEvidencesExcecuted == main.k) {
							if (!main.resultingStateList.contains(a.state)) {
								main.resultingStateList.add(a.state);
								if (main.resultingStateList.size() > 1) {
									out.println("MULTIPLE");
									processesdList = null;
									main = null;
									Q = null;
									continue testcase;
								}
							}
						} else {
							Q.add(a);
						}
					}
 
				}
				processesdList = null;
				
			}
 
			if (main.resultingStateList.size() == 0)
				out.println("CONFLICT");
			if (main.resultingStateList.size() == 1) {
				boolean isMultiple = false;
				String s = main.resultingStateList.get(0);
				if (s.contains("*")) {
					isMultiple = true;
				}
				if (isMultiple)
					out.println("MULTIPLE");
				else
					out.println("UNIQUE");
			}
			main = null;
			Q = null;
 
		}
		out.close();
	}
 
	public List<State> process(State state) throws CloneNotSupportedException {
		List<State> processedList = new ArrayList<State>();
		State newState1 = null;
		State newState2 = null;
		int[] evidence = evidences[state.noOfEvidencesExcecuted];
		int a = evidence[0];
		int b = evidence[1];
		int absValueA = Math.abs(a) - 1;
		int absValueB = Math.abs(b) - 1;
 
		// Case 1: 1st option is true
		if (state.state.charAt(absValueA) == '*') {
			newState1 = (State) state.clone();
			if (a > 0) {
				newState1.state = newState1.state.substring(0, absValueA) + "+"
						+ newState1.state.substring(absValueA + 1);
			}
			if (a < 0) {
				newState1.state = newState1.state.substring(0, absValueA) + "-"
						+ newState1.state.substring(absValueA + 1);
			}
 
		}
 
		if ((state.state.charAt(absValueA) == '+' && a > 0)
				|| (state.state.charAt(absValueA) == '-' && a < 0)) {
			newState1 = (State) state.clone();
		}
		if (newState1 != null) {
			newState1.noOfEvidencesExcecuted++;
			processedList.add(newState1);
		}
 
		// Case 2: 2nd option is true
		if (state.state.charAt(absValueB) == '*') {
			newState2 = (State) state.clone();
			if (b > 0) {
				newState2.state = newState2.state.substring(0, absValueB) + "+"
						+ newState2.state.substring(absValueB + 1);
			}
			if (b < 0) {
				newState2.state = newState2.state.substring(0, absValueB) + "-"
						+ newState2.state.substring(absValueB + 1);
			}
 
		}
 
		if ((state.state.charAt(absValueB) == '+' && b > 0)
				|| (state.state.charAt(absValueB) == '-' && b < 0)) {
			newState2 = (State) state.clone();
		}
 
		if (newState2 != null && !newState2.isSame(newState1)) {
			newState2.noOfEvidencesExcecuted++;
			processedList.add(newState2);
		}
		if (processedList.size() == 0) {
			processedList.add(State.SENTINEL_STATE);
		}
		return processedList;
	}
}
 
class State implements Cloneable {
	int noOfEvidencesExcecuted;
 
	String state;
 
	static State SENTINEL_STATE = new State(-1, null);
 
	State(int noOfEvidencesExcecuted, String state) {
		this.noOfEvidencesExcecuted = noOfEvidencesExcecuted;
		this.state = state;
	}
 
	public Object clone() throws CloneNotSupportedException {
		State clone = (State) super.clone();
		return clone;
	}
 
	public boolean isSame(State state) {
		if (state == null)
			return false;
		int stateLength = this.state.length();
		for (int i = 0; i < stateLength; i++) {
			if (this.state.charAt(i) != state.state.charAt(i)) {
				return false;
			}
 
		}
		return true;
	}
 
}