답안 #382547

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
382547	2021-03-27T16:07:54 Z	vijay	Tales of seafaring (POI13_mor)	Java 11	30 / 100	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 && visited[start][end][dist % 2]){
                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

Note: mor.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.

Subtask #1
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	138 ms	10616 KB	Output is correct
2	Correct	126 ms	10384 KB	Output is correct
3	Correct	143 ms	10336 KB	Output is correct
4	Execution timed out	3033 ms	23736 KB	Time limit exceeded

Subtask #2
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	167 ms	10736 KB	Output is correct
2	Correct	161 ms	11280 KB	Output is correct
3	Correct	188 ms	11436 KB	Output is correct
4	Execution timed out	3030 ms	23972 KB	Time limit exceeded

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	718 ms	18268 KB	Output is correct
2	Correct	239 ms	13028 KB	Output is correct
3	Correct	521 ms	17812 KB	Output is correct

Subtask #4
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	876 ms	28896 KB	Output is correct
2	Correct	716 ms	20000 KB	Output is correct
3	Correct	1002 ms	39768 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1822 ms	49388 KB	Output is correct
2	Correct	1532 ms	74748 KB	Output is correct
3	Correct	2187 ms	76696 KB	Output is correct

Subtask #6
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1041 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #7
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1392 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1288 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #9
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1321 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Runtime error	1311 ms	131072 KB	Execution killed with signal 9
2	Halted	0 ms	0 KB	-