Submission #382562

#TimeUsernameProblemLanguageResultExecution timeMemory
382562vijayTales of seafaring (POI13_mor)Java
30 / 100
3080 ms131072 KiB
import java.io.*; import java.util.*; public class mor { static ArrayList<Integer>[] adj; public static void main(String[] args) throws IOException, FileNotFoundException { // Scanner in = new Scanner(new File("seafaring.in")); InputReader in = new InputReader(); int N = in.nextInt(); int M = in.nextInt(); int K = in.nextInt(); adj = new ArrayList[N]; for(int i = 0; i < N; i++){ adj[i] = new ArrayList<>(); } int[][][] dp = new int[N][N][2]; for(int i = 0; i < N; i++){ for(int j = 0; j < N; j++){ Arrays.fill(dp[i][j], 1000000); } } for(int i = 0; i < M; i++){ int a = in.nextInt() - 1; int b = in.nextInt() - 1; dp[a][a][0] = 0; dp[b][b][0] = 0; adj[a].add(b); adj[b].add(a); } // check what the minimum odd path is and the minimum even path is for(int i = 0; i < N; i++){ PriorityQueue<State> pq = new PriorityQueue<>(); pq.add(new State(i, 0)); while(!pq.isEmpty()){ State curr = pq.poll(); if(dp[i][curr.position][curr.distance % 2] != curr.distance){ continue; } for(int ap: adj[curr.position]){ if(curr.distance + 1 < dp[i][ap][(curr.distance + 1)%2]){ dp[i][ap][(curr.distance + 1)%2] = Math.min(dp[i][ap][(curr.distance + 1) % 2], curr.distance + 1); pq.add(new State(ap, curr.distance + 1)); } } } } // for(int i = 0; i < N; i++){ // System.out.println("i: " + i); // for(int j = 0; j < N; j++){ // System.out.println(" j: " + j); // System.out.println(" " + Arrays.toString(dp[i][j])); // } // } for(int i = 0; i < K; i++){ int start = in.nextInt() - 1; int end = in.nextInt() - 1; int dist = in.nextInt(); // System.out.println(Arrays.toString(distances[start][end])); if(dp[start][end][dist % 2] <= dist && dp[start][end][dist % 2] != 1000000){ System.out.println("TAK"); } else { System.out.println("NIE"); } } } public static class State implements Comparable<State>{ int position; int distance; public State(int position, int distance){ this.position = position; this.distance = distance; } public int compareTo(State s){ return distance - s.distance; } } public static class InputReader { /** * The default size of the InputReader's buffer is 2<sup>16</sup>. */ private static final int DEFAULT_BUFFER_SIZE = 1 << 16; /** * The default stream for the InputReader is standard input. */ private static final InputStream DEFAULT_STREAM = System.in; /** * The maximum number of accurate decimal digits the method {@link #nextDoubleFast() nextDoubleFast()} can read. * Currently this value is set to 21 because it is the maximum number of digits a double precision float can have at the moment. */ private static final int MAX_DECIMAL_PRECISION = 21; // 'c' is used to refer to the current character in the stream private int c; // Variables associated with the byte buffer. private byte[] buf; private int bufferSize, bufIndex, numBytesRead; private InputStream stream; // End Of File (EOF) character private static final byte EOF = -1; // New line character: '\n' private static final byte NEW_LINE = 10; // Space character: ' ' private static final byte SPACE = 32; // Dash character: '-' private static final byte DASH = 45; // Dot character: '.' private static final byte DOT = 46; // A reusable character buffer when reading string data. private char[] charBuffer; // Primitive data type lookup tables used for optimizations private static byte[] bytes = new byte[58]; private static int[] ints = new int[58]; private static char[] chars = new char[128]; static { char ch = ' '; int value = 0; byte _byte = 0; for (int i = 48; i < 58; i++ ) bytes[i] = _byte++; for (int i = 48; i < 58; i++ ) ints[i] = value++; for (int i = 32; i < 128; i++ ) chars[i] = ch++; } // Primitive double lookup table used for optimizations. private static final double[][] doubles = { { 0.0d,0.00d,0.000d,0.0000d,0.00000d,0.000000d,0.0000000d,0.00000000d,0.000000000d,0.0000000000d,0.00000000000d,0.000000000000d,0.0000000000000d,0.00000000000000d,0.000000000000000d,0.0000000000000000d,0.00000000000000000d,0.000000000000000000d,0.0000000000000000000d,0.00000000000000000000d,0.000000000000000000000d }, { 0.1d,0.01d,0.001d,0.0001d,0.00001d,0.000001d,0.0000001d,0.00000001d,0.000000001d,0.0000000001d,0.00000000001d,0.000000000001d,0.0000000000001d,0.00000000000001d,0.000000000000001d,0.0000000000000001d,0.00000000000000001d,0.000000000000000001d,0.0000000000000000001d,0.00000000000000000001d,0.000000000000000000001d }, { 0.2d,0.02d,0.002d,0.0002d,0.00002d,0.000002d,0.0000002d,0.00000002d,0.000000002d,0.0000000002d,0.00000000002d,0.000000000002d,0.0000000000002d,0.00000000000002d,0.000000000000002d,0.0000000000000002d,0.00000000000000002d,0.000000000000000002d,0.0000000000000000002d,0.00000000000000000002d,0.000000000000000000002d }, { 0.3d,0.03d,0.003d,0.0003d,0.00003d,0.000003d,0.0000003d,0.00000003d,0.000000003d,0.0000000003d,0.00000000003d,0.000000000003d,0.0000000000003d,0.00000000000003d,0.000000000000003d,0.0000000000000003d,0.00000000000000003d,0.000000000000000003d,0.0000000000000000003d,0.00000000000000000003d,0.000000000000000000003d }, { 0.4d,0.04d,0.004d,0.0004d,0.00004d,0.000004d,0.0000004d,0.00000004d,0.000000004d,0.0000000004d,0.00000000004d,0.000000000004d,0.0000000000004d,0.00000000000004d,0.000000000000004d,0.0000000000000004d,0.00000000000000004d,0.000000000000000004d,0.0000000000000000004d,0.00000000000000000004d,0.000000000000000000004d }, { 0.5d,0.05d,0.005d,0.0005d,0.00005d,0.000005d,0.0000005d,0.00000005d,0.000000005d,0.0000000005d,0.00000000005d,0.000000000005d,0.0000000000005d,0.00000000000005d,0.000000000000005d,0.0000000000000005d,0.00000000000000005d,0.000000000000000005d,0.0000000000000000005d,0.00000000000000000005d,0.000000000000000000005d }, { 0.6d,0.06d,0.006d,0.0006d,0.00006d,0.000006d,0.0000006d,0.00000006d,0.000000006d,0.0000000006d,0.00000000006d,0.000000000006d,0.0000000000006d,0.00000000000006d,0.000000000000006d,0.0000000000000006d,0.00000000000000006d,0.000000000000000006d,0.0000000000000000006d,0.00000000000000000006d,0.000000000000000000006d }, { 0.7d,0.07d,0.007d,0.0007d,0.00007d,0.000007d,0.0000007d,0.00000007d,0.000000007d,0.0000000007d,0.00000000007d,0.000000000007d,0.0000000000007d,0.00000000000007d,0.000000000000007d,0.0000000000000007d,0.00000000000000007d,0.000000000000000007d,0.0000000000000000007d,0.00000000000000000007d,0.000000000000000000007d }, { 0.8d,0.08d,0.008d,0.0008d,0.00008d,0.000008d,0.0000008d,0.00000008d,0.000000008d,0.0000000008d,0.00000000008d,0.000000000008d,0.0000000000008d,0.00000000000008d,0.000000000000008d,0.0000000000000008d,0.00000000000000008d,0.000000000000000008d,0.0000000000000000008d,0.00000000000000000008d,0.000000000000000000008d }, { 0.9d,0.09d,0.009d,0.0009d,0.00009d,0.000009d,0.0000009d,0.00000009d,0.000000009d,0.0000000009d,0.00000000009d,0.000000000009d,0.0000000000009d,0.00000000000009d,0.000000000000009d,0.0000000000000009d,0.00000000000000009d,0.000000000000000009d,0.0000000000000000009d,0.00000000000000000009d,0.000000000000000000009d } }; /** * Create an InputReader that reads from standard input. */ public InputReader () { this(DEFAULT_STREAM, DEFAULT_BUFFER_SIZE); } /** * Create an InputReader that reads from standard input. * @param bufferSize The buffer size for this input reader. */ public InputReader(int bufferSize) { this(DEFAULT_STREAM, bufferSize); } /** * Create an InputReader that reads from standard input. * @param stream Takes an InputStream as a parameter to read from. */ public InputReader(InputStream stream) { this(stream, DEFAULT_BUFFER_SIZE); } /** * Create an InputReader that reads from standard input. * @param stream Takes an {@link java.io.InputStream#InputStream() InputStream} as a parameter to read from. * @param bufferSize The size of the buffer to use. */ public InputReader (InputStream stream, int bufferSize) { if (stream == null || bufferSize <= 0) throw new IllegalArgumentException(); buf = new byte[bufferSize]; charBuffer = new char[128]; this.bufferSize = bufferSize; this.stream = stream; } /** * Reads a single character from the input stream. * @return Returns the byte value of the next character in the buffer and EOF * at the end of the stream. * @throws IOException throws exception if there is no more data to read */ private byte read() throws IOException { if (numBytesRead == EOF) throw new IOException(); if (bufIndex >= numBytesRead) { bufIndex = 0; numBytesRead = stream.read(buf); if (numBytesRead == EOF) return EOF; } return buf[bufIndex++]; } /** * Read values from the input stream until you reach a character with a * higher ASCII value than 'token'. * @param token The token is a value which we use to stop reading junk out of * the stream. * @return Returns 0 if a value greater than the token was reached or -1 if * the end of the stream was reached. * @throws IOException Throws exception at end of stream. */ private int readJunk(int token) throws IOException { if (numBytesRead == EOF) return EOF; // Seek to the first valid position index do { while(bufIndex < numBytesRead) { if (buf[bufIndex] > token) return 0; bufIndex++; } // reload buffer numBytesRead = stream.read(buf); if (numBytesRead == EOF) return EOF; bufIndex = 0; } while(true); } /** * Reads a single byte from the input stream. * @return The next byte in the input stream * @throws IOException Throws exception at end of stream. */ public byte nextByte() throws IOException { return (byte) nextInt(); } /** * Reads a 32 bit signed integer from input stream. * @return The next integer value in the stream. * @throws IOException Throws exception at end of stream. */ public int nextInt() throws IOException { if (readJunk(DASH-1) == EOF) throw new IOException(); int sgn = 1, res = 0; c = buf[bufIndex]; if (c == DASH) { sgn = -1; bufIndex++; } do { while(bufIndex < numBytesRead) { if (buf[bufIndex] > SPACE) { res = (res<<3)+(res<<1); res += ints[buf[bufIndex++]]; } else { bufIndex++; return res*sgn; } } // Reload buffer numBytesRead = stream.read(buf); if (numBytesRead == EOF) return res*sgn; bufIndex = 0; } while(true); } /** * Reads a 64 bit signed long from input stream. * @return The next long value in the stream. * @throws IOException Throws exception at end of stream. */ public long nextLong() throws IOException { if (readJunk(DASH-1) == EOF) throw new IOException(); int sgn = 1; long res = 0L; c = buf[bufIndex]; if (c == DASH) { sgn = -1; bufIndex++; } do { while(bufIndex < numBytesRead) { if (buf[bufIndex] > SPACE) { res = (res<<3)+(res<<1); res += ints[buf[bufIndex++]]; } else { bufIndex++; return res*sgn; } } // Reload buffer numBytesRead = stream.read(buf); if (numBytesRead == EOF) return res*sgn; bufIndex = 0; } while(true); } /** * Doubles the size of the internal char buffer for strings */ private void doubleCharBufferSize() { char[] newBuffer = new char[charBuffer.length << 1]; for(int i = 0; i < charBuffer.length; i++) newBuffer[i] = charBuffer[i]; charBuffer = newBuffer; } /** * Reads a line from the input stream. * @return Returns a line from the input stream in the form a String not * including the new line character. Returns <code>null</code> when there are * no more lines. * @throws IOException Throws IOException when something terrible happens. */ public String nextLine() throws IOException { try { c=read(); } catch (IOException e) { return null; } if (c == NEW_LINE) return ""; // Empty line if (c == EOF) return null; // EOF int i = 0; charBuffer[i++] = (char)c; do { while(bufIndex < numBytesRead) { if (buf[bufIndex] != NEW_LINE) { if (i == charBuffer.length) doubleCharBufferSize(); charBuffer[i++] = (char) buf[bufIndex++]; } else { bufIndex++; return new String(charBuffer, 0, i); } } // Reload buffer numBytesRead = stream.read(buf); if (numBytesRead == EOF) return new String(charBuffer, 0, i); bufIndex = 0; } while(true); } // Reads a string of characters from the input stream. // The delimiter separating a string of characters is set to be: // any ASCII value <= 32 meaning any spaces, new lines, EOF, tabs... public String nextString() throws IOException { if (numBytesRead == EOF) return null; if (readJunk(SPACE) == EOF) return null; for(int i = 0;;) { while(bufIndex < numBytesRead) { if (buf[bufIndex] > SPACE) { if (i == charBuffer.length) doubleCharBufferSize(); charBuffer[i++] = (char) buf[bufIndex++]; } else { bufIndex++; return new String(charBuffer, 0, i); } } // Reload buffer numBytesRead = stream.read(buf); if (numBytesRead == EOF) return new String(charBuffer, 0, i); bufIndex = 0; } } // Returns an exact value a double value from the input stream. public double nextDouble() throws IOException { String doubleVal = nextString(); if (doubleVal == null) throw new IOException(); return Double.valueOf(doubleVal); } // Very quickly reads a double value from the input stream (~3x faster than nextDouble()). However, // this method may provide a slightly less accurate reading than .nextDouble() if there are a lot // of digits (~16+). In particular, it will only read double values with at most 21 digits after // the decimal point and the reading my be as inaccurate as ~5*10^-16 from the true value. public double nextDoubleFast() throws IOException { c = read(); int sgn = 1; while (c <= SPACE) c = read(); // while c is either: ' ', '\n', EOF if (c == DASH) { sgn = -1; c = read(); } double res = 0.0; // while c is not: ' ', '\n', '.' or -1 while (c > DOT) {res *= 10.0; res += ints[c]; c = read(); } if (c == DOT) { int i = 0; c = read(); // while c is digit and we are less than the maximum decimal precision while (c > SPACE && i < MAX_DECIMAL_PRECISION) { res += doubles[ints[c]][i++]; c = read(); } } return res * sgn; } // Read an array of n byte values public byte[] nextByteArray(int n) throws IOException { byte[] ar = new byte[n]; for (int i = 0; i < n; i++) ar[i] = nextByte(); return ar; } // Read an integer array of size n public int[] nextIntArray(int n) throws IOException { int[] ar = new int[n]; for (int i = 0; i < n; i++) ar[i] = nextInt(); return ar; } // Read a long array of size n public long[] nextLongArray(int n) throws IOException { long[] ar = new long[n]; for (int i = 0; i < n; i++) ar[i] = nextLong(); return ar; } // read an of doubles of size n public double[] nextDoubleArray(int n) throws IOException { double[] ar = new double[n]; for (int i = 0; i < n; i++) ar[i] = nextDouble(); return ar; } // Quickly read an array of doubles public double[] nextDoubleArrayFast(int n) throws IOException { double[] ar = new double[n]; for (int i = 0; i < n; i++) ar[i] = nextDoubleFast(); return ar; } // Read a string array of size n public String[] nextStringArray(int n) throws IOException { String[] ar = new String[n]; for (int i = 0; i < n; i++) { String str = nextString(); if (str == null) throw new IOException(); ar[i] = str; } return ar; } // Read a 1-based byte array of size n+1 public byte[] nextByteArray1(int n) throws IOException { byte[] ar = new byte[n+1]; for (int i = 1; i <= n; i++) ar[i] = nextByte(); return ar; } // Read a 1-based integer array of size n+1 public int[] nextIntArray1(int n) throws IOException { int[] ar = new int[n+1]; for (int i = 1; i <= n; i++) ar[i] = nextInt(); return ar; } // Read a 1-based long array of size n+1 public long[] nextLongArray1(int n) throws IOException { long[] ar = new long[n+1]; for (int i = 1; i <= n; i++) ar[i] = nextLong(); return ar; } // Read a 1-based double array of size n+1 public double[] nextDoubleArray1(int n) throws IOException { double[] ar = new double[n+1]; for (int i = 1; i <= n; i++) ar[i] = nextDouble(); return ar; } // Quickly read a 1-based double array of size n+1 public double[] nextDoubleArrayFast1(int n) throws IOException { double[] ar = new double[n+1]; for (int i = 1; i <= n; i++) ar[i] = nextDoubleFast(); return ar; } // Read a 1-based string array of size n+1 public String[] nextStringArray1(int n) throws IOException { String[] ar = new String[n+1]; for (int i = 1; i <= n; i++) ar[i] = nextString(); return ar; } // Read a two dimensional matrix of bytes of size rows x cols public byte[][] nextByteMatrix(int rows, int cols) throws IOException { byte[][] matrix = new byte[rows][cols]; for(int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) matrix[i][j] = nextByte(); return matrix; } // Read a two dimensional matrix of ints of size rows x cols public int[][] nextIntMatrix(int rows, int cols) throws IOException { int[][] matrix = new int[rows][cols]; for(int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) matrix[i][j] = nextInt(); return matrix; } // Read a two dimensional matrix of longs of size rows x cols public long[][] nextLongMatrix(int rows, int cols) throws IOException { long[][] matrix = new long[rows][cols]; for(int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) matrix[i][j] = nextLong(); return matrix; } // Read a two dimensional matrix of doubles of size rows x cols public double[][] nextDoubleMatrix(int rows, int cols) throws IOException { double[][] matrix = new double[rows][cols]; for(int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) matrix[i][j] = nextDouble(); return matrix; } // Quickly read a two dimensional matrix of doubles of size rows x cols public double[][] nextDoubleMatrixFast(int rows, int cols) throws IOException { double[][] matrix = new double[rows][cols]; for(int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) matrix[i][j] = nextDoubleFast(); return matrix; } // Read a two dimensional matrix of Strings of size rows x cols public String[][] nextStringMatrix(int rows, int cols) throws IOException { String[][] matrix = new String[rows][cols]; for(int i = 0; i < rows; i++) for (int j = 0; j < cols; j++) matrix[i][j] = nextString(); return matrix; } // Read a 1-based two dimensional matrix of bytes of size rows x cols public byte[][] nextByteMatrix1(int rows, int cols) throws IOException { byte[][] matrix = new byte[rows+1][cols+1]; for(int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++) matrix[i][j] = nextByte(); return matrix; } // Read a 1-based two dimensional matrix of ints of size rows x cols public int[][] nextIntMatrix1(int rows, int cols) throws IOException { int[][] matrix = new int[rows+1][cols+1]; for(int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++) matrix[i][j] = nextInt(); return matrix; } // Read a 1-based two dimensional matrix of longs of size rows x cols public long[][] nextLongMatrix1(int rows, int cols) throws IOException { long[][] matrix = new long[rows+1][cols+1]; for(int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++) matrix[i][j] = nextLong(); return matrix; } // Read a 1-based two dimensional matrix of doubles of size rows x cols public double[][] nextDoubleMatrix1(int rows, int cols) throws IOException { double[][] matrix = new double[rows+1][cols+1]; for(int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++) matrix[i][j] = nextDouble(); return matrix; } // Quickly read a 1-based two dimensional matrix of doubles of size rows x cols public double[][] nextDoubleMatrixFast1(int rows, int cols) throws IOException { double[][] matrix = new double[rows+1][cols+1]; for(int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++) matrix[i][j] = nextDoubleFast(); return matrix; } // Read a 1-based two dimensional matrix of Strings of size rows x cols public String[][] nextStringMatrix1(int rows, int cols) throws IOException { String[][] matrix = new String[rows+1][cols+1]; for(int i = 1; i <= rows; i++) for (int j = 1; j <= cols; j++) matrix[i][j] = nextString(); return matrix; } // Closes the input stream public void close() throws IOException { stream.close(); } } }

Compilation message (stderr)

Note: mor.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...