Submission #382541

#	Time	Username	Problem	Language	Result	Execution time	Memory
382541		vijay	Tales of seafaring (POI13_mor)	Java	0 / 100	2857 ms	131072 KiB

mor

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;
                }

                for(int ap: adj[curr.position]){
                    if(curr.distance + 1 < distances[i][ap][(int) (curr.distance + 1)%2]){
                        distances[i][curr.position][(int) (curr.distance % 2)] = Math.min(curr.distance, distances[i][curr.position][(int) (curr.distance % 2)]);
                        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 && distances[start][end][dist % 2] != Long.MAX_VALUE){
                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 (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 10
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10