oj.uz

Submission #794873

# Submission time Handle Problem Language Result Execution time Memory
794873 2023-07-27T01:57:41 Z sushikid Mecho (IOI09_mecho) Java 11
16 / 100
 159 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()[2]/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});
                        }
                    }
                }
            }
            if(visited[end[0]][end[1]]){
                ans = i;
            }
        }
        pw.println(ans);
        pw.close();
    }
}

Subtask #1
16.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 8364 KB Output is correct
2 Incorrect 49 ms 8460 KB Output isn't correct
3 Correct 48 ms 8456 KB Output is correct
4 Incorrect 49 ms 8420 KB Output isn't correct
5 Correct 50 ms 8212 KB Output is correct
6 Incorrect 49 ms 8200 KB Output isn't correct
7 Runtime error 104 ms 65536 KB Execution killed with signal 9
8 Correct 55 ms 9024 KB Output is correct
9 Correct 55 ms 9120 KB Output is correct
10 Correct 55 ms 8676 KB Output is correct
11 Correct 55 ms 9196 KB Output is correct
12 Incorrect 82 ms 12112 KB Output isn't correct
13 Correct 83 ms 11788 KB Output is correct
14 Correct 123 ms 14236 KB Output is correct
15 Incorrect 77 ms 11128 KB Output isn't correct
16 Incorrect 93 ms 12000 KB Output isn't correct
17 Incorrect 96 ms 11876 KB Output isn't correct
18 Incorrect 101 ms 12148 KB Output isn't correct
19 Incorrect 101 ms 12068 KB Output isn't correct
20 Incorrect 121 ms 13360 KB Output isn't correct
21 Incorrect 103 ms 12520 KB Output isn't correct
22 Incorrect 109 ms 14048 KB Output isn't correct
23 Incorrect 111 ms 13984 KB Output isn't correct
24 Incorrect 130 ms 14736 KB Output isn't correct
25 Incorrect 117 ms 14240 KB Output isn't correct
26 Incorrect 132 ms 14648 KB Output isn't correct
27 Incorrect 127 ms 14536 KB Output isn't correct
28 Incorrect 150 ms 14852 KB Output isn't correct
29 Incorrect 133 ms 14736 KB Output isn't correct
30 Incorrect 153 ms 15176 KB Output isn't correct
31 Incorrect 126 ms 15108 KB Output isn't correct
32 Incorrect 159 ms 15328 KB Output isn't correct
33 Runtime error 125 ms 65536 KB Execution killed with signal 9
34 Runtime error 105 ms 65536 KB Execution killed with signal 9
35 Runtime error 110 ms 65536 KB Execution killed with signal 9
36 Runtime error 103 ms 65536 KB Execution killed with signal 9
37 Runtime error 113 ms 65536 KB Execution killed with signal 9
38 Runtime error 118 ms 65536 KB Execution killed with signal 9
39 Runtime error 105 ms 65536 KB Execution killed with signal 9
40 Runtime error 100 ms 65536 KB Execution killed with signal 9
41 Runtime error 107 ms 65536 KB Execution killed with signal 9
42 Runtime error 110 ms 65536 KB Execution killed with signal 9
43 Runtime error 119 ms 65536 KB Execution killed with signal 9
44 Runtime error 113 ms 65536 KB Execution killed with signal 9
45 Runtime error 101 ms 65536 KB Execution killed with signal 9
46 Runtime error 110 ms 65536 KB Execution killed with signal 9
47 Runtime error 97 ms 65536 KB Execution killed with signal 9
48 Runtime error 108 ms 65536 KB Execution killed with signal 9
49 Runtime error 105 ms 65536 KB Execution killed with signal 9
50 Runtime error 105 ms 65536 KB Execution killed with signal 9
51 Runtime error 99 ms 65536 KB Execution killed with signal 9
52 Runtime error 107 ms 65536 KB Execution killed with signal 9
53 Runtime error 105 ms 65536 KB Execution killed with signal 9
54 Runtime error 116 ms 65536 KB Execution killed with signal 9
55 Runtime error 101 ms 65536 KB Execution killed with signal 9
56 Runtime error 98 ms 65536 KB Execution killed with signal 9
57 Runtime error 102 ms 65536 KB Execution killed with signal 9
58 Runtime error 104 ms 65536 KB Execution killed with signal 9
59 Runtime error 100 ms 65536 KB Execution killed with signal 9
60 Runtime error 105 ms 65536 KB Execution killed with signal 9
61 Runtime error 97 ms 65536 KB Execution killed with signal 9
62 Runtime error 105 ms 65536 KB Execution killed with signal 9
63 Runtime error 105 ms 65536 KB Execution killed with signal 9
64 Runtime error 104 ms 65536 KB Execution killed with signal 9
65 Runtime error 102 ms 65536 KB Execution killed with signal 9
66 Runtime error 113 ms 65536 KB Execution killed with signal 9
67 Runtime error 98 ms 65536 KB Execution killed with signal 9
68 Runtime error 104 ms 65536 KB Execution killed with signal 9
69 Runtime error 98 ms 65536 KB Execution killed with signal 9
70 Runtime error 97 ms 65536 KB Execution killed with signal 9
71 Runtime error 107 ms 65536 KB Execution killed with signal 9
72 Runtime error 96 ms 65536 KB Execution killed with signal 9
73 Runtime error 100 ms 65536 KB Execution killed with signal 9
74 Runtime error 97 ms 65536 KB Execution killed with signal 9
75 Runtime error 98 ms 65536 KB Execution killed with signal 9
76 Runtime error 102 ms 65536 KB Execution killed with signal 9
77 Runtime error 103 ms 65536 KB Execution killed with signal 9
78 Runtime error 96 ms 65536 KB Execution killed with signal 9
79 Runtime error 100 ms 65536 KB Execution killed with signal 9
80 Runtime error 107 ms 65536 KB Execution killed with signal 9
81 Runtime error 100 ms 65536 KB Execution killed with signal 9
82 Runtime error 112 ms 65536 KB Execution killed with signal 9
83 Runtime error 91 ms 65536 KB Execution killed with signal 9
84 Runtime error 100 ms 65536 KB Execution killed with signal 9
85 Runtime error 110 ms 65536 KB Execution killed with signal 9
86 Runtime error 121 ms 65536 KB Execution killed with signal 9
87 Runtime error 94 ms 65536 KB Execution killed with signal 9
88 Runtime error 95 ms 65536 KB Execution killed with signal 9
89 Runtime error 121 ms 65536 KB Execution killed with signal 9
90 Runtime error 108 ms 65536 KB Execution killed with signal 9
91 Runtime error 102 ms 65536 KB Execution killed with signal 9
92 Runtime error 116 ms 65536 KB Execution killed with signal 9