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
Submission Time | |
---|---|
Task | B - コメント |
User | ixxa |
Language | Java (OpenJDK 1.7.0) |
Score | 90 |
Code Size | 4791 Byte |
Status | AC |
Exec Time | 1926 ms |
Memory | 47380 KB |
Compile Error
Note: ./Main.java uses unchecked or unsafe operations. Note: Recompile with -Xlint:unchecked for details.
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||
---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 30 / 30 | 60 / 60 | ||||||
Status |
|
|
|
Set Name | Test Cases |
---|---|
Sample | sample_01.txt, sample_02.txt |
Subtask1 | sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt |
Subtask2 | subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_15.txt, subtask1_16.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt, subtask2_10.txt, subtask2_11.txt, subtask2_12.txt, subtask2_13.txt, subtask2_14.txt, subtask2_15.txt, subtask2_16.txt, subtask2_17.txt, subtask2_18.txt, subtask2_19.txt, subtask2_20.txt, subtask2_21.txt, subtask2_22.txt, subtask2_23.txt, subtask2_24.txt, subtask2_25.txt, subtask2_26.txt, subtask2_27.txt, subtask2_28.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
sample_01.txt | AC | 550 ms | 20720 KB |
sample_02.txt | AC | 382 ms | 20792 KB |
subtask1_01.txt | AC | 386 ms | 20692 KB |
subtask1_02.txt | AC | 496 ms | 26104 KB |
subtask1_03.txt | AC | 488 ms | 26692 KB |
subtask1_04.txt | AC | 472 ms | 25700 KB |
subtask1_05.txt | AC | 460 ms | 27384 KB |
subtask1_06.txt | AC | 441 ms | 24632 KB |
subtask1_07.txt | AC | 417 ms | 23244 KB |
subtask1_08.txt | AC | 419 ms | 23708 KB |
subtask1_09.txt | AC | 388 ms | 20780 KB |
subtask1_10.txt | AC | 485 ms | 25492 KB |
subtask1_11.txt | AC | 484 ms | 26036 KB |
subtask1_12.txt | AC | 443 ms | 27052 KB |
subtask1_13.txt | AC | 465 ms | 25560 KB |
subtask1_14.txt | AC | 451 ms | 25924 KB |
subtask1_15.txt | AC | 407 ms | 22128 KB |
subtask1_16.txt | AC | 481 ms | 25728 KB |
subtask2_01.txt | AC | 493 ms | 24828 KB |
subtask2_02.txt | AC | 990 ms | 39860 KB |
subtask2_03.txt | AC | 628 ms | 31472 KB |
subtask2_04.txt | AC | 690 ms | 37408 KB |
subtask2_05.txt | AC | 466 ms | 24676 KB |
subtask2_06.txt | AC | 468 ms | 26136 KB |
subtask2_07.txt | AC | 431 ms | 23344 KB |
subtask2_08.txt | AC | 493 ms | 25576 KB |
subtask2_09.txt | AC | 1074 ms | 47308 KB |
subtask2_10.txt | AC | 654 ms | 33408 KB |
subtask2_11.txt | AC | 1069 ms | 47380 KB |
subtask2_12.txt | AC | 686 ms | 34768 KB |
subtask2_13.txt | AC | 511 ms | 27200 KB |
subtask2_14.txt | AC | 1032 ms | 40860 KB |
subtask2_15.txt | AC | 562 ms | 30212 KB |
subtask2_16.txt | AC | 1164 ms | 45560 KB |
subtask2_17.txt | AC | 676 ms | 34640 KB |
subtask2_18.txt | AC | 1202 ms | 46236 KB |
subtask2_19.txt | AC | 855 ms | 35276 KB |
subtask2_20.txt | AC | 1372 ms | 36656 KB |
subtask2_21.txt | AC | 1926 ms | 36324 KB |
subtask2_22.txt | AC | 1809 ms | 36536 KB |
subtask2_23.txt | AC | 942 ms | 31468 KB |
subtask2_24.txt | AC | 1293 ms | 37252 KB |
subtask2_25.txt | AC | 1816 ms | 35352 KB |
subtask2_26.txt | AC | 599 ms | 28764 KB |
subtask2_27.txt | AC | 991 ms | 42808 KB |
subtask2_28.txt | AC | 949 ms | 37656 KB |