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
long[][][] distances = new long[N][N][2];
for(int i = 0; i < N; i++){
for(int j = 0; j < N; j++){
Arrays.fill(distances[i][j], Long.MAX_VALUE);
}
}
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(distances[i][curr.position][(int) (curr.distance % 2)] < curr.distance){
continue;
}
distances[i][curr.position][(int) (curr.distance % 2)] = Math.min(curr.distance, distances[i][curr.position][(int) (curr.distance % 2)]);
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(distances[start][end][dist % 2] <= dist){
System.out.println("TAK");
} else {
System.out.println("NIE");
}
}
}
public static class State implements Comparable<State>{
int position;
long distance;
public State(int position, long distance){
this.position = position;
this.distance = distance;
}
public int compareTo(State s){
return Long.compare(distance, s.distance);
}
}
}
Compilation message
Note: mor.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
124 ms |
10852 KB |
Output is correct |
2 |
Incorrect |
127 ms |
10616 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
166 ms |
11244 KB |
Output is correct |
2 |
Correct |
150 ms |
11228 KB |
Output is correct |
3 |
Incorrect |
256 ms |
15404 KB |
Output isn't correct |
4 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
737 ms |
16896 KB |
Output is correct |
2 |
Correct |
296 ms |
15840 KB |
Output is correct |
3 |
Correct |
518 ms |
16008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
888 ms |
24100 KB |
Output is correct |
2 |
Correct |
743 ms |
18120 KB |
Output is correct |
3 |
Correct |
1973 ms |
28132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Execution timed out |
3027 ms |
40088 KB |
Time limit exceeded |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1112 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1183 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1179 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1245 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
1198 ms |
131072 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |