oj.uz

Submission #794962

# Submission time Handle Problem Language Result Execution time Memory
794962 2023-07-27T04:36:50 Z sushikid Mecho (IOI09_mecho) Java 11
53 / 100
 391 ms 26804 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, s;
    private static char[][] grid;
    private static int[][] bees;
    private static int[] start, end;

    private static boolean valid(int x, int y){
        return 0 <= x && x < n && 0 <= y && y < n;
    }
    private static boolean check(int x){
        if(bees[start[0]][start[1]] <= x){
            return false;
        }

        boolean[][] dist = new boolean[n][n];
        Queue<int[]> cur = new LinkedList<>();
        cur.add(new int[]{start[0], start[1], 0});

        dist[start[0]][start[1]] = true;
        while(!cur.isEmpty()){
            int[] z = cur.poll();
            for (int i = 0; i < 4; i++) {
                int fx = z[0] + dx[i];
                int fy = z[1] + dy[i];
                if(valid(fx, fy) && !dist[fx][fy] && grid[fx][fy] != 'T' && (z[2] + 1)/s + x < bees[fx][fy]){
                    dist[fx][fy] = true;
                    cur.add(new int[]{fx, fy, z[2] + 1});
                }
            }
        }
        return dist[end[0]][end[1]];
    }
    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()); s = Integer.parseInt(st.nextToken());

        grid = new char[n][n];
        start = new int[]{-1, -1}; end = new int[]{-1, -1};
        Queue<int[]> hives = new LinkedList<>();
        bees = new int[n][n];

        for (int i = 0; i < n; i++) {
            Arrays.fill(bees[i], Integer.MAX_VALUE);
        }
        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});
                    bees[i][j] = 0;
                }
                grid[i][j] = str.charAt(j);
            }
        }
        while(!hives.isEmpty()){
            int[] x = hives.poll();
            for (int i = 0; i < 4; i++) {
                int fx = x[0] + dx[i];
                int fy = x[1] + dy[i];
                if(valid(fx, fy) && bees[fx][fy] == Integer.MAX_VALUE && (grid[fx][fy] == 'G' || grid[fx][fy] == 'M')){
                    bees[fx][fy] = x[2] + 1;
                    hives.add(new int[]{fx, fy, x[2] + 1});
                }
            }
        }
        int left = 0;
        int right = 2 * n;
        while(left < right){
            int mid = left + (right - left + 1)/2;
            if(check(mid)){
                left = mid;
            }
            else{
                right = mid - 1;
            }
        }
        if(check(right)){
            pw.println(right);
        }
        else{
            pw.println(-1);
        }
        pw.close();
    }
}

Subtask #1
53.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 8204 KB Output is correct
2 Correct 49 ms 8248 KB Output is correct
3 Correct 49 ms 8384 KB Output is correct
4 Correct 48 ms 8300 KB Output is correct
5 Correct 59 ms 8236 KB Output is correct
6 Correct 53 ms 8192 KB Output is correct
7 Correct 296 ms 24404 KB Output is correct
8 Correct 49 ms 8388 KB Output is correct
9 Correct 52 ms 8480 KB Output is correct
10 Correct 50 ms 8420 KB Output is correct
11 Correct 51 ms 8400 KB Output is correct
12 Incorrect 56 ms 9012 KB Output isn't correct
13 Correct 64 ms 8396 KB Output is correct
14 Correct 94 ms 11132 KB Output is correct
15 Incorrect 54 ms 8324 KB Output isn't correct
16 Incorrect 60 ms 8372 KB Output isn't correct
17 Incorrect 58 ms 8564 KB Output isn't correct
18 Incorrect 55 ms 8356 KB Output isn't correct
19 Incorrect 59 ms 8680 KB Output isn't correct
20 Incorrect 57 ms 8656 KB Output isn't correct
21 Incorrect 65 ms 10560 KB Output isn't correct
22 Incorrect 67 ms 10444 KB Output isn't correct
23 Incorrect 73 ms 10516 KB Output isn't correct
24 Incorrect 78 ms 10700 KB Output isn't correct
25 Incorrect 84 ms 11080 KB Output isn't correct
26 Incorrect 85 ms 11252 KB Output isn't correct
27 Incorrect 75 ms 10924 KB Output isn't correct
28 Incorrect 84 ms 11736 KB Output isn't correct
29 Incorrect 84 ms 11384 KB Output isn't correct
30 Incorrect 84 ms 11796 KB Output isn't correct
31 Incorrect 92 ms 11488 KB Output isn't correct
32 Incorrect 101 ms 12832 KB Output isn't correct
33 Incorrect 195 ms 14764 KB Output isn't correct
34 Incorrect 216 ms 15216 KB Output isn't correct
35 Correct 209 ms 15948 KB Output is correct
36 Incorrect 183 ms 15564 KB Output isn't correct
37 Incorrect 219 ms 17340 KB Output isn't correct
38 Correct 219 ms 16608 KB Output is correct
39 Incorrect 204 ms 16232 KB Output isn't correct
40 Incorrect 227 ms 18168 KB Output isn't correct
41 Correct 237 ms 17520 KB Output is correct
42 Incorrect 208 ms 17796 KB Output isn't correct
43 Incorrect 236 ms 18896 KB Output isn't correct
44 Correct 250 ms 18392 KB Output is correct
45 Incorrect 224 ms 19392 KB Output isn't correct
46 Incorrect 255 ms 19776 KB Output isn't correct
47 Correct 264 ms 19208 KB Output is correct
48 Incorrect 219 ms 19500 KB Output isn't correct
49 Incorrect 288 ms 19912 KB Output isn't correct
50 Correct 276 ms 19660 KB Output is correct
51 Incorrect 247 ms 20676 KB Output isn't correct
52 Incorrect 286 ms 21112 KB Output isn't correct
53 Correct 300 ms 19992 KB Output is correct
54 Incorrect 248 ms 22056 KB Output isn't correct
55 Incorrect 305 ms 22312 KB Output isn't correct
56 Correct 330 ms 22436 KB Output is correct
57 Incorrect 255 ms 22812 KB Output isn't correct
58 Incorrect 314 ms 23100 KB Output isn't correct
59 Correct 381 ms 23252 KB Output is correct
60 Incorrect 268 ms 24200 KB Output isn't correct
61 Incorrect 330 ms 24420 KB Output isn't correct
62 Correct 389 ms 24284 KB Output is correct
63 Correct 311 ms 24640 KB Output is correct
64 Correct 388 ms 24140 KB Output is correct
65 Correct 391 ms 24172 KB Output is correct
66 Correct 364 ms 24572 KB Output is correct
67 Correct 341 ms 24308 KB Output is correct
68 Correct 244 ms 22656 KB Output is correct
69 Correct 233 ms 21608 KB Output is correct
70 Correct 228 ms 22144 KB Output is correct
71 Correct 234 ms 21028 KB Output is correct
72 Correct 225 ms 19616 KB Output is correct
73 Correct 237 ms 26408 KB Output is correct
74 Correct 259 ms 26252 KB Output is correct
75 Correct 333 ms 26420 KB Output is correct
76 Correct 301 ms 26444 KB Output is correct
77 Correct 325 ms 26804 KB Output is correct
78 Correct 312 ms 26192 KB Output is correct
79 Correct 340 ms 26148 KB Output is correct
80 Correct 338 ms 26176 KB Output is correct
81 Correct 340 ms 26080 KB Output is correct
82 Correct 307 ms 26368 KB Output is correct
83 Correct 319 ms 25740 KB Output is correct
84 Correct 317 ms 25904 KB Output is correct
85 Correct 341 ms 25608 KB Output is correct
86 Correct 311 ms 25636 KB Output is correct
87 Correct 336 ms 26004 KB Output is correct
88 Correct 320 ms 25444 KB Output is correct
89 Correct 353 ms 25212 KB Output is correct
90 Correct 343 ms 25308 KB Output is correct
91 Correct 334 ms 25512 KB Output is correct
92 Correct 374 ms 25332 KB Output is correct