Submission #490564

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
490564	2021-11-28T02:27:14 Z	vijay	Mecho (IOI09_mecho)	Java 11	24 / 100	890 ms	65540 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 = 1000000;
        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	96 ms	10908 KB	Output is correct
2	Correct	104 ms	10044 KB	Output is correct
3	Correct	95 ms	10236 KB	Output is correct
4	Correct	93 ms	10316 KB	Output is correct
5	Correct	97 ms	10208 KB	Output is correct
6	Correct	218 ms	20896 KB	Output is correct
7	Runtime error	851 ms	65540 KB	Execution killed with signal 9
8	Incorrect	113 ms	10212 KB	Output isn't correct
9	Correct	383 ms	48452 KB	Output is correct
10	Correct	251 ms	22252 KB	Output is correct
11	Runtime error	433 ms	65540 KB	Execution killed with signal 9
12	Incorrect	130 ms	10820 KB	Output isn't correct
13	Correct	135 ms	11068 KB	Output is correct
14	Runtime error	488 ms	65540 KB	Execution killed with signal 9
15	Correct	100 ms	10212 KB	Output is correct
16	Runtime error	464 ms	65536 KB	Execution killed with signal 9
17	Correct	99 ms	10148 KB	Output is correct
18	Runtime error	433 ms	65540 KB	Execution killed with signal 9
19	Correct	113 ms	10160 KB	Output is correct
20	Runtime error	454 ms	65536 KB	Execution killed with signal 9
21	Correct	103 ms	10272 KB	Output is correct
22	Runtime error	477 ms	65540 KB	Execution killed with signal 9
23	Correct	114 ms	10464 KB	Output is correct
24	Runtime error	459 ms	65540 KB	Execution killed with signal 9
25	Correct	120 ms	10428 KB	Output is correct
26	Runtime error	472 ms	65540 KB	Execution killed with signal 9
27	Correct	121 ms	10440 KB	Output is correct
28	Runtime error	495 ms	65540 KB	Execution killed with signal 9
29	Correct	137 ms	11320 KB	Output is correct
30	Runtime error	472 ms	65536 KB	Execution killed with signal 9
31	Correct	163 ms	12788 KB	Output is correct
32	Runtime error	490 ms	65540 KB	Execution killed with signal 9
33	Correct	253 ms	16300 KB	Output is correct
34	Runtime error	622 ms	65540 KB	Execution killed with signal 9
35	Runtime error	626 ms	65536 KB	Execution killed with signal 9
36	Correct	259 ms	16536 KB	Output is correct
37	Runtime error	642 ms	65540 KB	Execution killed with signal 9
38	Runtime error	593 ms	65540 KB	Execution killed with signal 9
39	Correct	255 ms	16848 KB	Output is correct
40	Runtime error	610 ms	65540 KB	Execution killed with signal 9
41	Runtime error	656 ms	65536 KB	Execution killed with signal 9
42	Correct	262 ms	17028 KB	Output is correct
43	Runtime error	707 ms	65536 KB	Execution killed with signal 9
44	Runtime error	666 ms	65536 KB	Execution killed with signal 9
45	Correct	271 ms	17588 KB	Output is correct
46	Runtime error	634 ms	65540 KB	Execution killed with signal 9
47	Runtime error	652 ms	65540 KB	Execution killed with signal 9
48	Correct	284 ms	17924 KB	Output is correct
49	Runtime error	663 ms	65540 KB	Execution killed with signal 9
50	Runtime error	670 ms	65540 KB	Execution killed with signal 9
51	Correct	284 ms	18088 KB	Output is correct
52	Runtime error	653 ms	65540 KB	Execution killed with signal 9
53	Runtime error	712 ms	65540 KB	Execution killed with signal 9
54	Correct	290 ms	18740 KB	Output is correct
55	Runtime error	664 ms	65536 KB	Execution killed with signal 9
56	Runtime error	642 ms	65540 KB	Execution killed with signal 9
57	Correct	295 ms	19756 KB	Output is correct
58	Runtime error	659 ms	65540 KB	Execution killed with signal 9
59	Runtime error	660 ms	65540 KB	Execution killed with signal 9
60	Correct	289 ms	20572 KB	Output is correct
61	Runtime error	611 ms	65540 KB	Execution killed with signal 9
62	Runtime error	687 ms	65540 KB	Execution killed with signal 9
63	Runtime error	640 ms	65540 KB	Execution killed with signal 9
64	Runtime error	704 ms	65540 KB	Execution killed with signal 9
65	Runtime error	708 ms	65536 KB	Execution killed with signal 9
66	Runtime error	656 ms	65540 KB	Execution killed with signal 9
67	Runtime error	637 ms	65540 KB	Execution killed with signal 9
68	Runtime error	683 ms	65536 KB	Execution killed with signal 9
69	Runtime error	674 ms	65540 KB	Execution killed with signal 9
70	Runtime error	692 ms	65536 KB	Execution killed with signal 9
71	Runtime error	722 ms	65540 KB	Execution killed with signal 9
72	Runtime error	708 ms	65540 KB	Execution killed with signal 9
73	Runtime error	799 ms	65540 KB	Execution killed with signal 9
74	Runtime error	806 ms	65540 KB	Execution killed with signal 9
75	Runtime error	820 ms	65540 KB	Execution killed with signal 9
76	Runtime error	817 ms	65540 KB	Execution killed with signal 9
77	Runtime error	861 ms	65540 KB	Execution killed with signal 9
78	Runtime error	890 ms	65540 KB	Execution killed with signal 9
79	Runtime error	877 ms	65536 KB	Execution killed with signal 9
80	Runtime error	868 ms	65540 KB	Execution killed with signal 9
81	Runtime error	816 ms	65540 KB	Execution killed with signal 9
82	Runtime error	836 ms	65540 KB	Execution killed with signal 9
83	Runtime error	841 ms	65536 KB	Execution killed with signal 9
84	Runtime error	831 ms	65536 KB	Execution killed with signal 9
85	Runtime error	842 ms	65536 KB	Execution killed with signal 9
86	Runtime error	831 ms	65536 KB	Execution killed with signal 9
87	Runtime error	808 ms	65540 KB	Execution killed with signal 9
88	Runtime error	842 ms	65540 KB	Execution killed with signal 9
89	Runtime error	848 ms	65540 KB	Execution killed with signal 9
90	Runtime error	843 ms	65540 KB	Execution killed with signal 9
91	Runtime error	860 ms	65540 KB	Execution killed with signal 9
92	Runtime error	852 ms	65540 KB	Execution killed with signal 9