# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
382543 | 2021-03-27T16:02:38 Z | vijay | Tales of seafaring (POI13_mor) | Java 11 | 2124 ms | 131072 KB |
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")); Scanner in = new Scanner(System.in); 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<>(); } for(int i = 0; i < M; i++){ int a = in.nextInt() - 1; int b = in.nextInt() - 1; adj[a].add(b); adj[b].add(a); } // check what the minimum odd path is and the minimum even path is int[][][] dp = new int[N][N][2]; boolean[][][] visited = new boolean[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 < N; i++){ PriorityQueue<State> pq = new PriorityQueue<>(); pq.add(new State(i, 0)); while(!pq.isEmpty()){ State curr = pq.poll(); if(visited[i][curr.position][curr.distance % 2]){ continue; } visited[i][curr.position][curr.distance % 2] = true; dp[i][curr.position][curr.distance % 2] = curr.distance; for(int ap: adj[curr.position]){ pq.add(new State(ap, curr.distance + 1)); } } } 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; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 123 ms | 10724 KB | Output is correct |
2 | Incorrect | 121 ms | 10476 KB | Output isn't correct |
3 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 149 ms | 10900 KB | Output is correct |
2 | Correct | 149 ms | 11228 KB | Output is correct |
3 | Incorrect | 187 ms | 11524 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 693 ms | 16796 KB | Output is correct |
2 | Correct | 226 ms | 13276 KB | Output is correct |
3 | Correct | 483 ms | 16504 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 836 ms | 28616 KB | Output is correct |
2 | Correct | 683 ms | 18532 KB | Output is correct |
3 | Correct | 979 ms | 39044 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1721 ms | 49608 KB | Output is correct |
2 | Correct | 1411 ms | 74852 KB | Output is correct |
3 | Incorrect | 2124 ms | 76700 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1026 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1320 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1284 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1300 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1330 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |