Submission #338183

---

Source Code Expand

import java.io.*;
import java.math.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws Exception {
		new Main().solve();
	}
	void solve() throws Exception {
		FastScanner in = new FastScanner(System.in);

		int INF = Integer.MAX_VALUE / 2;

		int n = in.nextInt();
		int Lmin = INF;
		String[] s = new String[n];
		for (int i = 0; i < n; i++) {
			s[i] = in.next();
			Lmin = Math.min(Lmin, s[i].length());
		}

		int GN = n + n + 2;
		int S = GN - 2;
		int T = GN - 1;
		int A = 0;
		int B = n;

		// nei, cap
		int[][] cap = new int[GN][GN];
		LinkedList<Integer>[] nei = new LinkedList[GN];
		for (int i = 0; i < nei.length; i++) {
			nei[i] = new LinkedList<Integer>();
		}



		for (char ch = 'a'; ch <= 'z'; ch++) {

			// init
			// Q, qcnt, id, done
			Queue<Integer> Q = new ArrayDeque<Integer>();
			for (int i = 0; i < n; i++) {
				Q.add(1);
			}
			int qcnt = n;
			boolean[] done = new boolean[GN];

			for (int i = 0; i < nei.length; i++) {
				nei[i].clear();
				Arrays.fill(cap[i], 0);
			}
			for (int i = 0; i < n; i++) {
				for (int k = 0; k < n; k++) {
					if (s[k].length() > i && s[k].charAt(i) == ch) {
						nei[i].add(k + B);
						nei[k + B].add(i);
						cap[i][k + B] = 1;
					}
				}
			}
			for (int i = A; i < B; i++) {
				nei[S].add(i);
				nei[i].add(S);
				cap[S][i] = 1;
			}
			for (int i = B; i < S; i++) {
				nei[i].add(T);
				nei[T].add(i);
				cap[i][T] = 1;
			}

			// flow
			int curFlow = 0;
			for (int ei = n; ei - n + 1 <= Lmin; ei++) {
				if (qcnt == n) {// ?
					while (true) {
						Arrays.fill(done, false);
						int f = (int) flow(S, T, INF, done, cap, nei);
						curFlow += f;
						if (f == 0) {
							break;
						}
					}
				}
				if (curFlow == n) {
					// ok
					System.out.println("YES");
					return;
				} else {

					// /////////////
					// update
					int E = ei % n;
					// del
					if (cap[E][S] > 0) {
						// back
						Arrays.fill(done, false);
						flow(T, E, INF, done, cap, nei);
						curFlow--;
					}
					for (Integer i2 : nei[E]) {
						cap[E][i2] = cap[i2][E] = 0;
						nei[i2].remove(i2);
					}
					nei[E].clear();
					cap[E][S] = 0;
					cap[S][E] = 1;

					qcnt -= Q.remove();
					int qq = 0;
					for (int k = 0; k < n; k++) {
						if (s[k].length() > ei && s[k].charAt(ei) == ch) {
							nei[E].add(k + B);
							nei[k + B].add(E);
							cap[E][k + B] = 1;
							qq = 1;
						}
					}
					Q.add(qq);
					qcnt += qq;
				}
			}
		}
		System.out.println("NO");
	}

	// /////////////////////////////////////
	// flow
	// call : flow(start, goal, INF, new boolean[N], cap, nei)
	long flow(int idx, int goal, int mf, boolean[] done, int[][] cap, List<Integer>[] nei) {
		done[idx] = true;
		if (idx == goal) {
			// ok
			return mf;
		} else {
			for (int ni : nei[idx]) {
				long f;
				if (!done[ni] && cap[idx][ni] > 0 && (f = flow(ni, goal, Math.min(mf, cap[idx][ni]), done, cap, nei)) > 0) {
					// ok
					cap[idx][ni] -= f;
					cap[ni][idx] += f;
					return f;
				}
			}
			return 0;
		}
	}

	//
	//
	//
	//
	//
	//
	//
	//
	//
	//
	//
	//
	class FastScanner {

		private InputStream _stream;
		private byte[] _buf = new byte[1024];
		private int _curChar;
		private int _numChars;
		private StringBuilder _sb = new StringBuilder();

		FastScanner(InputStream stream) {
			this._stream = stream;
		}

		public int read() {
			if (_numChars == -1) throw new InputMismatchException();
			if (_curChar >= _numChars) {
				_curChar = 0;
				try {
					_numChars = _stream.read(_buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (_numChars <= 0) return -1;
			}
			return _buf[_curChar++];
		}

		public String next() {
			int c = read();
			while (isWhitespace(c)) {
				c = read();
			}
			_sb.setLength(0);
			do {
				_sb.appendCodePoint(c);
				c = read();
			} while (!isWhitespace(c));
			return _sb.toString();
		}

		public int nextInt() {
			return (int) nextLong();
		}
		public long nextLong() {
			int c = read();
			while (isWhitespace(c)) {
				c = read();
			}
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9') throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isWhitespace(c));
			return res * sgn;
		}

		public boolean isWhitespace(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
	}
}
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//

Submission Info

Compile Error

Note: ./Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Judge Result