oj.uz

Submission #794860

# Submission time Handle Problem Language Result Execution time Memory
794860 2023-07-27T01:46:43 Z sushikid Mecho (IOI09_mecho) Java 11
3 / 100
 168 ms 65536 KB 
import java.util.*;
import java.io.*;

public class mecho {
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};

    private static int n;
    private static char[][] grid;

    private static boolean mark(int x, int y, boolean[][] arr){
        for (int i = 0; i < 4; i++) {
            int fx = x + dx[i];
            int fy = y + dy[i];
            if(check(fx, fy) && arr[fx][fy] && grid[fx][fy] != 'T'){
                return true;
            }
        }
        return arr[x][y];
    }
    private static boolean check(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        n = Integer.parseInt(st.nextToken()); int s = Integer.parseInt(st.nextToken());

        grid = new char[n][n];
        int[] start = {-1, -1}; int[] end = {-1, -1};
        Queue<int[]> hives = new LinkedList<>();
        int ans = -1;
        boolean[][][] times = new boolean[2 * n][n][n];

        for (int i = 0; i < n; i++) {
            String str = r.readLine();
            for (int j = 0; j < n; j++) {
                if(str.charAt(j) == 'M'){
                    start = new int[]{i, j};
                }
                if(str.charAt(j) == 'D'){
                    end = new int[]{i, j};
                }
                if(str.charAt(j) == 'H'){
                    hives.add(new int[]{i, j, 0});
                    times[0][i][j] = true;
                }
                grid[i][j] = str.charAt(j);
            }
        }
        for (int i = 1; i < 2 * n; i++) {
            for (int j = 0; j < n; j++) {
                for (int j2 = 0; j2 < n; j2++) {
                    if(grid[j][j2] == 'T'){
                        continue;
                    }
                    times[i][j][j2] = mark(j, j2, times[i - 1]);
                }
            }
        }
        for (int i = 0; i < 2 * n; i++) {
            Queue<int[]> cur = new LinkedList<>();
            cur.add(new int[]{start[0], start[1], 0});
            boolean[][] visited = new boolean[n][n]; 
            visited[start[0]][start[1]] = true;
            for (int j = i; j < 2 * n; j++) {
                while(!cur.isEmpty() && Math.ceil(cur.peek()[0]/s) <= j - i){
                    int[] x = cur.poll();
                    if(times[j][x[0]][x[1]]){
                        continue;
                    }
                    for (int k = 0; k < 4; k++) {
                        int fx = x[0] + dx[k];
                        int fy = x[1] + dy[k];
                        if(check(fx, fy) && !times[j][fx][fy] && !visited[fx][fy] && grid[fx][fy] != 'T'){
                            visited[fx][fy] = true;
                            cur.add(new int[]{fx, fy, x[2] + 1});
                        }
                    }
                }
            }
            // for(boolean[] e : visited){
            //     System.out.println(Arrays.toString(e));
            // }
            // System.out.println("===");
            if(visited[end[0]][end[1]]){
                ans = i;
            }
        }
        pw.println(ans);
        pw.close();
    }
}

Subtask #1
3.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 8648 KB Output is correct
2 Incorrect 50 ms 8584 KB Output isn't correct
3 Incorrect 49 ms 8412 KB Output isn't correct
4 Incorrect 49 ms 8452 KB Output isn't correct
5 Correct 58 ms 8564 KB Output is correct
6 Incorrect 51 ms 8236 KB Output isn't correct
7 Runtime error 103 ms 65536 KB Execution killed with signal 9
8 Correct 58 ms 8868 KB Output is correct
9 Incorrect 56 ms 9000 KB Output isn't correct
10 Incorrect 55 ms 8896 KB Output isn't correct
11 Incorrect 55 ms 9088 KB Output isn't correct
12 Incorrect 86 ms 12380 KB Output isn't correct
13 Incorrect 85 ms 11612 KB Output isn't correct
14 Incorrect 125 ms 14460 KB Output isn't correct
15 Incorrect 102 ms 12120 KB Output isn't correct
16 Incorrect 100 ms 11932 KB Output isn't correct
17 Incorrect 108 ms 12348 KB Output isn't correct
18 Incorrect 99 ms 12532 KB Output isn't correct
19 Incorrect 106 ms 12852 KB Output isn't correct
20 Incorrect 106 ms 13868 KB Output isn't correct
21 Incorrect 129 ms 13780 KB Output isn't correct
22 Incorrect 110 ms 13616 KB Output isn't correct
23 Incorrect 128 ms 14852 KB Output isn't correct
24 Incorrect 116 ms 14232 KB Output isn't correct
25 Incorrect 132 ms 14792 KB Output isn't correct
26 Incorrect 122 ms 14416 KB Output isn't correct
27 Incorrect 151 ms 14824 KB Output isn't correct
28 Incorrect 141 ms 14768 KB Output isn't correct
29 Incorrect 149 ms 15036 KB Output isn't correct
30 Incorrect 142 ms 14924 KB Output isn't correct
31 Incorrect 168 ms 15312 KB Output isn't correct
32 Incorrect 144 ms 15272 KB Output isn't correct
33 Runtime error 106 ms 65536 KB Execution killed with signal 9
34 Runtime error 114 ms 65536 KB Execution killed with signal 9
35 Runtime error 112 ms 65536 KB Execution killed with signal 9
36 Runtime error 99 ms 65536 KB Execution killed with signal 9
37 Runtime error 104 ms 65536 KB Execution killed with signal 9
38 Runtime error 102 ms 65536 KB Execution killed with signal 9
39 Runtime error 124 ms 65536 KB Execution killed with signal 9
40 Runtime error 100 ms 65536 KB Execution killed with signal 9
41 Runtime error 103 ms 65536 KB Execution killed with signal 9
42 Runtime error 105 ms 65536 KB Execution killed with signal 9
43 Runtime error 105 ms 65536 KB Execution killed with signal 9
44 Runtime error 107 ms 65536 KB Execution killed with signal 9
45 Runtime error 107 ms 65536 KB Execution killed with signal 9
46 Runtime error 100 ms 65536 KB Execution killed with signal 9
47 Runtime error 105 ms 65536 KB Execution killed with signal 9
48 Runtime error 104 ms 65536 KB Execution killed with signal 9
49 Runtime error 96 ms 65536 KB Execution killed with signal 9
50 Runtime error 106 ms 65536 KB Execution killed with signal 9
51 Runtime error 112 ms 65536 KB Execution killed with signal 9
52 Runtime error 103 ms 65536 KB Execution killed with signal 9
53 Runtime error 105 ms 65536 KB Execution killed with signal 9
54 Runtime error 100 ms 65536 KB Execution killed with signal 9
55 Runtime error 107 ms 65536 KB Execution killed with signal 9
56 Runtime error 94 ms 65536 KB Execution killed with signal 9
57 Runtime error 96 ms 65536 KB Execution killed with signal 9
58 Runtime error 100 ms 65536 KB Execution killed with signal 9
59 Runtime error 116 ms 65536 KB Execution killed with signal 9
60 Runtime error 106 ms 65536 KB Execution killed with signal 9
61 Runtime error 95 ms 65536 KB Execution killed with signal 9
62 Runtime error 112 ms 65536 KB Execution killed with signal 9
63 Runtime error 103 ms 65536 KB Execution killed with signal 9
64 Runtime error 94 ms 65536 KB Execution killed with signal 9
65 Runtime error 100 ms 65536 KB Execution killed with signal 9
66 Runtime error 97 ms 65536 KB Execution killed with signal 9
67 Runtime error 102 ms 65536 KB Execution killed with signal 9
68 Runtime error 101 ms 65536 KB Execution killed with signal 9
69 Runtime error 104 ms 65536 KB Execution killed with signal 9
70 Runtime error 99 ms 65536 KB Execution killed with signal 9
71 Runtime error 104 ms 65536 KB Execution killed with signal 9
72 Runtime error 97 ms 65536 KB Execution killed with signal 9
73 Runtime error 103 ms 65536 KB Execution killed with signal 9
74 Runtime error 104 ms 65536 KB Execution killed with signal 9
75 Runtime error 94 ms 65536 KB Execution killed with signal 9
76 Runtime error 102 ms 65536 KB Execution killed with signal 9
77 Runtime error 111 ms 65536 KB Execution killed with signal 9
78 Runtime error 110 ms 65536 KB Execution killed with signal 9
79 Runtime error 106 ms 65536 KB Execution killed with signal 9
80 Runtime error 105 ms 65536 KB Execution killed with signal 9
81 Runtime error 96 ms 65536 KB Execution killed with signal 9
82 Runtime error 104 ms 65536 KB Execution killed with signal 9
83 Runtime error 98 ms 65536 KB Execution killed with signal 9
84 Runtime error 117 ms 65536 KB Execution killed with signal 9
85 Runtime error 110 ms 65536 KB Execution killed with signal 9
86 Runtime error 99 ms 65536 KB Execution killed with signal 9
87 Runtime error 102 ms 65536 KB Execution killed with signal 9
88 Runtime error 99 ms 65536 KB Execution killed with signal 9
89 Runtime error 98 ms 65536 KB Execution killed with signal 9
90 Runtime error 96 ms 65536 KB Execution killed with signal 9
91 Runtime error 107 ms 65536 KB Execution killed with signal 9
92 Runtime error 116 ms 65536 KB Execution killed with signal 9