Submission #490565

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490565	2021-11-28T02:51:11 Z	vijay	Mecho (IOI09_mecho)	Java 11	24 / 100	856 ms	65544 KB

mecho

import java.io.*;
import java.util.*;

public class mecho {
    static int N, S;
    static int[][] distFromHive;
    static int startX, startY, endX, endY;
    static int[] dX, dY;
    static boolean[][] forest;
    public static void main(String[] args) throws IOException, FileNotFoundException {
        Scanner in = new Scanner(System.in);
        // Scanner in = new Scanner(new File("test.in"));

        N = in.nextInt();
        S = in.nextInt();

        forest = new boolean[N][N];

        PriorityQueue<State> pq = new PriorityQueue<>();

        for(int i = 0; i < N; i++){
            String line = in.next();
            for(int j = 0; j < N; j++){
                int cchar = line.charAt(j);
                if(cchar == 'T'){
                    forest[i][j] = true;
                } else if (cchar == 'M'){
                    startX = i;
                    startY = j;
                } else if (cchar == 'D'){
                    endX = i;
                    endY = j;
                } else if (cchar == 'H'){
                    pq.add(new State(i, j, 0));
                }
            } 
        }

        distFromHive = new int[N][N];
        for(int i = 0; i < N; i++){
            Arrays.fill(distFromHive[i], -1);
        }

        dX = new int[] {-1, 1, 0, 0};
        dY = new int[] {0, 0, -1, 1};

        while(!pq.isEmpty()){
            State curr = pq.poll();
            if(distFromHive[curr.x][curr.y] != -1){
                continue;
            }
            distFromHive[curr.x][curr.y] = curr.dist;
            for(int i = 0; i < 4; i++){
                int nX = curr.x + dX[i];
                int nY = curr.y + dY[i];
                if(nX < 0 || nX >= N || nY < 0 || nY >= N || forest[nX][nY]){
                    continue;
                }
                pq.add(new State(nX, nY, curr.dist + 1));
            }
        }

        // for(int i = 0; i < N; i++){
        //     System.out.println(Arrays.toString(distFromHive[i]));
        // }

        int a = 0;
        int b = 640000000;
        while(a != b){
            int mid = (a + b + 1)/2;
            if(works(mid)){
                a = mid;
            } else {
                b = mid - 1;
            }
        }

        System.out.println(a);
    }

    public static boolean works(int wait){
        PriorityQueue<State> pq = new PriorityQueue<>();
        pq.add(new State(startX, startY, wait * S));
        boolean[][] visited = new boolean[N][N];
        while(!pq.isEmpty()){
            State curr = pq.poll();
            if(visited[curr.x][curr.y]){
                continue;
            }

            if(curr.x == endX && curr.y == endY){
                // System.out.println("get to " + curr.x + " " + curr.y + " in " + curr.dist + " vs. " + distFromHive[curr.x][curr.y]);
                return true;
            }

            if(distFromHive[curr.x][curr.y] * S <= curr.dist){
                continue;
            }

            for(int i = 0; i < 4; i++){
                int nX = curr.x + dX[i];
                int nY = curr.y + dY[i];
                if(nX < 0 || nX >= N || nY < 0 || nY >= N || forest[nX][nY]){
                    continue;
                }
                pq.add(new State(nX, nY, curr.dist + 1));
            }
        }
        return false;
    }

    public static class State implements Comparable<State>{
        int x, y, dist;
        public State(int x, int y, int dist){
            this.x = x;
            this.y = y;
            this.dist = dist;
        }
        public int compareTo(State s){
            return dist - s.dist;
        }
    }
}

Subtask #1

24.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	98 ms	10212 KB	Output is correct
2	Correct	97 ms	10088 KB	Output is correct
3	Correct	98 ms	10172 KB	Output is correct
4	Correct	97 ms	10152 KB	Output is correct
5	Correct	98 ms	10028 KB	Output is correct
6	Correct	222 ms	19916 KB	Output is correct
7	Runtime error	797 ms	65536 KB	Execution killed with signal 9
8	Incorrect	107 ms	10236 KB	Output isn't correct
9	Runtime error	411 ms	65540 KB	Execution killed with signal 9
10	Correct	191 ms	14908 KB	Output is correct
11	Runtime error	443 ms	65540 KB	Execution killed with signal 9
12	Incorrect	123 ms	10908 KB	Output isn't correct
13	Correct	133 ms	11132 KB	Output is correct
14	Runtime error	495 ms	65540 KB	Execution killed with signal 9
15	Correct	97 ms	10300 KB	Output is correct
16	Runtime error	467 ms	65540 KB	Execution killed with signal 9
17	Correct	105 ms	10104 KB	Output is correct
18	Runtime error	449 ms	65540 KB	Execution killed with signal 9
19	Correct	108 ms	10212 KB	Output is correct
20	Runtime error	426 ms	65540 KB	Execution killed with signal 9
21	Correct	107 ms	10296 KB	Output is correct
22	Runtime error	456 ms	65540 KB	Execution killed with signal 9
23	Correct	111 ms	10452 KB	Output is correct
24	Runtime error	457 ms	65540 KB	Execution killed with signal 9
25	Correct	116 ms	10196 KB	Output is correct
26	Runtime error	468 ms	65540 KB	Execution killed with signal 9
27	Correct	125 ms	10504 KB	Output is correct
28	Runtime error	461 ms	65540 KB	Execution killed with signal 9
29	Correct	145 ms	11268 KB	Output is correct
30	Runtime error	475 ms	65540 KB	Execution killed with signal 9
31	Correct	156 ms	12808 KB	Output is correct
32	Runtime error	489 ms	65536 KB	Execution killed with signal 9
33	Correct	247 ms	16248 KB	Output is correct
34	Runtime error	666 ms	65540 KB	Execution killed with signal 9
35	Runtime error	625 ms	65540 KB	Execution killed with signal 9
36	Correct	244 ms	16468 KB	Output is correct
37	Runtime error	643 ms	65540 KB	Execution killed with signal 9
38	Runtime error	623 ms	65540 KB	Execution killed with signal 9
39	Correct	253 ms	16848 KB	Output is correct
40	Runtime error	661 ms	65536 KB	Execution killed with signal 9
41	Runtime error	624 ms	65540 KB	Execution killed with signal 9
42	Correct	252 ms	16896 KB	Output is correct
43	Runtime error	659 ms	65536 KB	Execution killed with signal 9
44	Runtime error	623 ms	65540 KB	Execution killed with signal 9
45	Correct	263 ms	17344 KB	Output is correct
46	Runtime error	658 ms	65540 KB	Execution killed with signal 9
47	Runtime error	665 ms	65540 KB	Execution killed with signal 9
48	Correct	271 ms	17436 KB	Output is correct
49	Runtime error	656 ms	65540 KB	Execution killed with signal 9
50	Runtime error	689 ms	65540 KB	Execution killed with signal 9
51	Correct	283 ms	17632 KB	Output is correct
52	Runtime error	639 ms	65540 KB	Execution killed with signal 9
53	Runtime error	679 ms	65540 KB	Execution killed with signal 9
54	Correct	305 ms	18612 KB	Output is correct
55	Runtime error	624 ms	65536 KB	Execution killed with signal 9
56	Runtime error	722 ms	65540 KB	Execution killed with signal 9
57	Correct	285 ms	19364 KB	Output is correct
58	Runtime error	655 ms	65540 KB	Execution killed with signal 9
59	Runtime error	704 ms	65540 KB	Execution killed with signal 9
60	Correct	294 ms	19940 KB	Output is correct
61	Runtime error	593 ms	65536 KB	Execution killed with signal 9
62	Runtime error	665 ms	65536 KB	Execution killed with signal 9
63	Runtime error	672 ms	65536 KB	Execution killed with signal 9
64	Runtime error	710 ms	65540 KB	Execution killed with signal 9
65	Runtime error	715 ms	65544 KB	Execution killed with signal 9
66	Runtime error	700 ms	65540 KB	Execution killed with signal 9
67	Runtime error	714 ms	65540 KB	Execution killed with signal 9
68	Runtime error	643 ms	65540 KB	Execution killed with signal 9
69	Runtime error	646 ms	65540 KB	Execution killed with signal 9
70	Runtime error	633 ms	65540 KB	Execution killed with signal 9
71	Runtime error	733 ms	65536 KB	Execution killed with signal 9
72	Runtime error	639 ms	65540 KB	Execution killed with signal 9
73	Runtime error	842 ms	65540 KB	Execution killed with signal 9
74	Runtime error	806 ms	65540 KB	Execution killed with signal 9
75	Runtime error	838 ms	65536 KB	Execution killed with signal 9
76	Runtime error	794 ms	65536 KB	Execution killed with signal 9
77	Runtime error	820 ms	65540 KB	Execution killed with signal 9
78	Runtime error	829 ms	65540 KB	Execution killed with signal 9
79	Runtime error	849 ms	65540 KB	Execution killed with signal 9
80	Runtime error	845 ms	65540 KB	Execution killed with signal 9
81	Runtime error	840 ms	65536 KB	Execution killed with signal 9
82	Runtime error	856 ms	65540 KB	Execution killed with signal 9
83	Runtime error	855 ms	65540 KB	Execution killed with signal 9
84	Runtime error	830 ms	65540 KB	Execution killed with signal 9
85	Runtime error	833 ms	65540 KB	Execution killed with signal 9
86	Runtime error	817 ms	65540 KB	Execution killed with signal 9
87	Runtime error	816 ms	65540 KB	Execution killed with signal 9
88	Runtime error	841 ms	65540 KB	Execution killed with signal 9
89	Runtime error	833 ms	65540 KB	Execution killed with signal 9
90	Runtime error	825 ms	65540 KB	Execution killed with signal 9
91	Runtime error	816 ms	65540 KB	Execution killed with signal 9
92	Runtime error	820 ms	65540 KB	Execution killed with signal 9