Submission #320514

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
320514	2020-11-09T02:29:36 Z	anishrajeev	Mecho (IOI09_mecho)	Java 11	14 / 100	980 ms	65568 KB

mecho

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

public class mecho {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader bf = new BufferedReader(new FileReader("tester.in"));
        PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));
        StringTokenizer stk = new StringTokenizer(bf.readLine());
        int N = Integer.parseInt(stk.nextToken());
        int S = Integer.parseInt(stk.nextToken());
        String[][] grid = new String[N][N];
        LinkedList<pair> list = new LinkedList<>();
        int[][] bees = new int[N][N];
        int startx = 0, starty = 0, homex = 0, homey = 0;
        for(int i = 0; i < N; i++){
            String line = bf.readLine();
            String[] str = line.split("");
            Arrays.fill(bees[i], Integer.MAX_VALUE);
            for(int c = 0; c < N; c++){
                grid[i][c] = str[c];
                if(grid[i][c].equals("H")){
                    list.add(new pair(i, c, 0));
                    bees[i][c] = 0;
                }
                if(grid[i][c].equals("M")){
                    startx = i;
                    starty = c;
                }
                if(grid[i][c].equals("D")){
                    homex = i;
                    homey = c;
                }
            }
        }
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        boolean[][] visited = new boolean[N][N];
        int counter = 0;
        while(!list.isEmpty()){
            pair p = list.pop();
            if(p.x == homex && p.y == homey)continue;
            if(grid[p.x][p.y].equals("T"))continue;
            bees[p.x][p.y] = Math.min(bees[p.x][p.y], p.t+S);
            if(visited[p.x][p.y])continue;
            visited[p.x][p.y] = true;
            for(int i = 0; i < 4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(N <= nx || nx < 0 || N <= ny || ny < 0)continue;
                list.add(new pair(nx, ny, bees[p.x][p.y]));
            }
            counter++;
        }
        bees[homex][homey] = Integer.MAX_VALUE;
        int start = 0, end = 10000000;
        while(start != end){
            int mid = (start+end+1)/2;
            if(verify(bees, grid, mid, startx, starty, homex, homey, N, S))start = mid;
            else end = mid-1;
        }
        System.out.println(start);
    }
    public static boolean verify(int[][] bees, String[][] grid, int time, int startx, int starty, int homex, int homey, int N, int S){
        Stack<pair> stack = new Stack<>();
        stack.push(new pair(startx, starty, time*S));
        int[] dx = new int[]{0, 1, 0, -1};
        int[] dy = new int[]{1, 0, -1, 0};
        int max = 0;
        for(int i = 0; i < N; i++){
            for(int c = 0; c < N; c++){
                if(bees[i][c]!=Integer.MAX_VALUE)max = Math.max(max, bees[i][c]);
            }
        }
        boolean[][][] visited = new boolean[N][N][max];
        while(!stack.isEmpty()){
            pair p = stack.pop();
            if(p.t >= max || visited[p.x][p.y][p.t])continue;
            visited[p.x][p.y][p.t] = true;
            for(int i = 0; i < 4; i++){
                int nx = p.x+dx[i];
                int ny = p.y+dy[i];
                if(N <= nx || nx < 0 || N <= ny || ny < 0)continue;
                if(bees[nx][ny] <= p.t)continue;
                if(grid[nx][ny].equals("T")||grid[nx][ny].equals("H"))continue;
                if(bees[nx][ny] <= p.t+1)continue;
                stack.push(new pair(nx, ny, p.t+1));
            }
        }
        for(int i = 0; i < max; i++){
            if(visited[homex][homey][i])return true;
        }
        return false;
    }
    public static class pair{
        int x, y, t;
        public pair(int a, int b, int c){
            x = a;
            y = b;
            t = c;
        }
    }
}

Subtask #1

14.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	86 ms	12292 KB	Output isn't correct
2	Correct	82 ms	11440 KB	Output is correct
3	Incorrect	89 ms	11572 KB	Output isn't correct
4	Incorrect	92 ms	11748 KB	Output isn't correct
5	Correct	81 ms	11620 KB	Output is correct
6	Correct	87 ms	11696 KB	Output is correct
7	Runtime error	888 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
8	Incorrect	88 ms	11700 KB	Output isn't correct
9	Correct	108 ms	12600 KB	Output is correct
10	Correct	96 ms	11976 KB	Output is correct
11	Correct	95 ms	11988 KB	Output is correct
12	Incorrect	162 ms	34008 KB	Output isn't correct
13	Incorrect	201 ms	23912 KB	Output isn't correct
14	Incorrect	325 ms	42128 KB	Output isn't correct
15	Correct	103 ms	13816 KB	Output is correct
16	Correct	116 ms	21276 KB	Output is correct
17	Correct	150 ms	17376 KB	Output is correct
18	Correct	217 ms	39292 KB	Output is correct
19	Correct	142 ms	21964 KB	Output is correct
20	Correct	248 ms	59372 KB	Output is correct
21	Correct	209 ms	38360 KB	Output is correct
22	Runtime error	184 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
23	Runtime error	300 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
24	Runtime error	183 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
25	Runtime error	206 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
26	Runtime error	184 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
27	Runtime error	213 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
28	Runtime error	194 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
29	Runtime error	217 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Runtime error	207 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
31	Runtime error	208 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
32	Runtime error	200 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
33	Runtime error	709 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
34	Runtime error	619 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
35	Runtime error	732 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
36	Runtime error	749 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
37	Runtime error	660 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
38	Runtime error	716 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
39	Runtime error	783 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
40	Runtime error	788 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
41	Runtime error	885 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
42	Runtime error	828 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
43	Runtime error	798 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
44	Runtime error	971 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
45	Runtime error	793 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
46	Runtime error	817 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
47	Runtime error	980 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
48	Runtime error	914 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
49	Runtime error	891 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
50	Runtime error	892 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
51	Runtime error	887 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
52	Runtime error	746 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
53	Runtime error	860 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
54	Runtime error	724 ms	65568 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
55	Runtime error	765 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
56	Runtime error	788 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
57	Runtime error	804 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
58	Runtime error	642 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
59	Runtime error	846 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
60	Runtime error	748 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
61	Runtime error	853 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
62	Runtime error	785 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
63	Runtime error	811 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
64	Runtime error	761 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
65	Runtime error	750 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
66	Runtime error	714 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
67	Runtime error	785 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
68	Runtime error	739 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
69	Runtime error	620 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
70	Runtime error	793 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
71	Runtime error	736 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
72	Runtime error	789 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
73	Runtime error	800 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
74	Runtime error	672 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
75	Runtime error	837 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
76	Runtime error	685 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
77	Runtime error	807 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
78	Runtime error	674 ms	65556 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
79	Runtime error	702 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
80	Runtime error	821 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
81	Runtime error	788 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
82	Runtime error	799 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
83	Runtime error	831 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
84	Runtime error	853 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
85	Runtime error	837 ms	65536 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
86	Runtime error	738 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
87	Runtime error	808 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
88	Runtime error	776 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
89	Runtime error	765 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
90	Runtime error	800 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
91	Runtime error	821 ms	65540 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
92	Runtime error	795 ms	65544 KB	Execution killed with signal 9 (could be triggered by violating memory limits)