Submission #337917
Source Code Expand
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.io.InputStreamReader; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.PriorityQueue; import java.util.Set; import java.util.SortedMap; import java.util.StringTokenizer; import java.util.TreeMap; import java.util.TreeSet; public class Main { public static boolean dfs(final int n, final int deep, final int using, final int index, String[] inputs, boolean[] used){ if(deep >= n){ return true; } for(int next = 0; next < n; next++){ final int next_index = index + 1; if(used[next]){ continue; } //System.out.println(deep + " : " + inputs[using] + "[" + index + "] " + " -> " + inputs[next] + "[" + next_index + "]"); if(inputs[next].length() <= next_index){ continue; }else if(inputs[next].charAt(next_index) != inputs[using].charAt(index)){ continue; } used[next] = true; if(dfs(n, deep + 1, next, next_index, inputs, used)){ return true; } used[next] = false; } return false; } public static void main(String[] args) throws IOException { Scanner sc = new Scanner(System.in); final int n = sc.nextInt(); if(n > 52){ return; } String[] inputs = new String[n]; for(int i = 0; i < n; i++){ inputs[i] = sc.next(); } boolean[][] contains = new boolean[n][26]; for(int i = 0; i < n; i++){ for(char c : inputs[i].toCharArray()){ contains[i][c - 'a'] = true; } } boolean[] used = new boolean[n]; for(int last = 0; last < n; last++){ final int size = inputs[last].length(); used[last] = true; for(int index = 0; index < size; index++){ boolean flag = false; for(int other = 0; other < n; other++){ if(other == last){ continue; } if(!contains[other][inputs[last].charAt(index) - 'a']){ flag = true; break; } } if(flag){ continue; } if(dfs(n, 1, last, index, inputs, used)){ System.out.println("YES"); return; } } used[last] = false; } System.out.println("NO"); } public static class Scanner { private BufferedReader br; private StringTokenizer tok; public Scanner(InputStream is) throws IOException { br = new BufferedReader(new InputStreamReader(is)); } private void getLine() throws IOException { while (!hasNext()) { tok = new StringTokenizer(br.readLine()); } } private boolean hasNext() { return tok != null && tok.hasMoreTokens(); } public String next() throws IOException { getLine(); return tok.nextToken(); } public int nextInt() throws IOException { return Integer.parseInt(next()); } public long nextLong() throws IOException { return Long.parseLong(next()); } public void close() throws IOException { br.close(); } } }
Submission Info
Submission Time | |
---|---|
Task | B - コメント |
User | mondatto |
Language | Java (OpenJDK 1.7.0) |
Score | 0 |
Code Size | 3057 Byte |
Status | WA |
Exec Time | 2036 ms |
Memory | 24940 KB |
Judge Result
Set Name | Sample | Subtask1 | Subtask2 | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 0 / 30 | 0 / 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 | 401 ms | 20840 KB |
sample_02.txt | AC | 402 ms | 20692 KB |
subtask1_01.txt | AC | 396 ms | 20596 KB |
subtask1_02.txt | AC | 412 ms | 20952 KB |
subtask1_03.txt | AC | 412 ms | 20868 KB |
subtask1_04.txt | AC | 411 ms | 21028 KB |
subtask1_05.txt | AC | 399 ms | 20524 KB |
subtask1_06.txt | AC | 430 ms | 22092 KB |
subtask1_07.txt | AC | 410 ms | 20948 KB |
subtask1_08.txt | AC | 433 ms | 22184 KB |
subtask1_09.txt | AC | 401 ms | 20656 KB |
subtask1_10.txt | AC | 415 ms | 20940 KB |
subtask1_11.txt | AC | 413 ms | 20888 KB |
subtask1_12.txt | AC | 434 ms | 22176 KB |
subtask1_13.txt | TLE | 2036 ms | 22352 KB |
subtask1_14.txt | AC | 399 ms | 20616 KB |
subtask1_15.txt | AC | 433 ms | 21996 KB |
subtask1_16.txt | AC | 415 ms | 20960 KB |
subtask2_01.txt | WA | 404 ms | 20660 KB |
subtask2_02.txt | WA | 395 ms | 20652 KB |
subtask2_03.txt | WA | 400 ms | 20648 KB |
subtask2_04.txt | WA | 399 ms | 20664 KB |
subtask2_05.txt | WA | 400 ms | 20648 KB |
subtask2_06.txt | WA | 396 ms | 20528 KB |
subtask2_07.txt | AC | 530 ms | 24940 KB |
subtask2_08.txt | WA | 427 ms | 20628 KB |
subtask2_09.txt | WA | 428 ms | 20588 KB |
subtask2_10.txt | WA | 434 ms | 20660 KB |
subtask2_11.txt | WA | 405 ms | 20548 KB |
subtask2_12.txt | WA | 398 ms | 20660 KB |
subtask2_13.txt | WA | 401 ms | 20536 KB |
subtask2_14.txt | WA | 398 ms | 20528 KB |
subtask2_15.txt | WA | 402 ms | 20664 KB |
subtask2_16.txt | WA | 399 ms | 20652 KB |
subtask2_17.txt | AC | 1544 ms | 24816 KB |
subtask2_18.txt | WA | 396 ms | 20660 KB |
subtask2_19.txt | TLE | 2036 ms | 24608 KB |
subtask2_20.txt | WA | 399 ms | 20524 KB |
subtask2_21.txt | WA | 542 ms | 20532 KB |
subtask2_22.txt | WA | 394 ms | 20656 KB |
subtask2_23.txt | WA | 404 ms | 20664 KB |
subtask2_24.txt | WA | 402 ms | 20656 KB |
subtask2_25.txt | WA | 401 ms | 20532 KB |
subtask2_26.txt | WA | 399 ms | 20528 KB |
subtask2_27.txt | WA | 400 ms | 20656 KB |
subtask2_28.txt | WA | 396 ms | 20656 KB |