# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
382544 | 2021-03-27T16:06:37 Z | vijay | Tales of seafaring (POI13_mor) | Java 11 | 3000 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<>(); for(int ap: adj[i]){ pq.add(new State(ap, 1)); } 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 | 122 ms | 10724 KB | Output is correct |
2 | Correct | 124 ms | 10552 KB | Output is correct |
3 | Correct | 143 ms | 10648 KB | Output is correct |
4 | Execution timed out | 3065 ms | 23880 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 153 ms | 10948 KB | Output is correct |
2 | Correct | 173 ms | 11340 KB | Output is correct |
3 | Correct | 188 ms | 11624 KB | Output is correct |
4 | Execution timed out | 3064 ms | 24276 KB | Time limit exceeded |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 708 ms | 17628 KB | Output is correct |
2 | Correct | 246 ms | 13244 KB | Output is correct |
3 | Correct | 514 ms | 17656 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 839 ms | 28980 KB | Output is correct |
2 | Correct | 772 ms | 19920 KB | Output is correct |
3 | Correct | 985 ms | 39560 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1730 ms | 49424 KB | Output is correct |
2 | Correct | 1459 ms | 75036 KB | Output is correct |
3 | Correct | 2175 ms | 76816 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 996 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1343 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1305 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1375 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Runtime error | 1341 ms | 131072 KB | Execution killed with signal 9 |
2 | Halted | 0 ms | 0 KB | - |