oj.uz

Submission #815860

# Submission time Handle Problem Language Result Execution time Memory
815860 2023-08-09T01:36:05 Z powervic08 Mecho (IOI09_mecho) Java 11
41 / 100
 661 ms 47924 KB 
import java.util.*;
import java.io.*;

public class mecho {

    static int[] dx = {-1, 1, 0, 0};
    static int[] dy = {0, 0, -1, 1};
    static int S;

    public static void main(String[] args) throws IOException {
        BufferedReader f = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter out = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(f.readLine());
        int n = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        int[][] grid = new int[n][n];
        int starti = 0, startj = 0, endi = 0, endj = 0;
        for (int i = 0; i < n; i++) {
            String s = f.readLine();
            for (int j = 0; j < n; j++) {
                if (s.charAt(j) == 'H') grid[i][j] = 1;
                else if (s.charAt(j) == 'T') grid[i][j] = 2;
                else if (s.charAt(j) == 'M') {
                    starti = i;
                    startj = j;
                } else if (s.charAt(j) == 'D') {
                    endi = i;
                    endj = j;
                }
            }
        }
        out.println(maximumMinutes(grid, starti, startj, endi, endj));
        out.close();
        f.close();
    }

    public static int maximumMinutes(int[][] grid, int starti, int startj, int endi, int endj) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<Node> q = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    q.add(new Node(i, j, 0));
                }
            }
        }
        int[][] dists = new int[n][m];
        for (int i = 0; i < n; i++) {
            Arrays.fill(dists[i], Integer.MAX_VALUE);
        }
        while (!q.isEmpty()) {
            Node p = q.poll();
            if (p.dist >= dists[p.i][p.j]) {
                continue;
            }
            dists[p.i][p.j] = (int) p.dist;
            for (int i = 0; i < 4; i++) {
                int newi = dx[i] + p.i;
                int newj = dy[i] + p.j;
                if (inRange(newi, newj, grid)) {
                    if (grid[newi][newj] != 2) {
                        q.add(new Node(newi, newj, p.dist + 1));
                    }
                }
            }
        }
        int l = -1;
        int r = n * n;
        while (l < r) {
            int mid = (l + r + 1) / 2;
            if (works(mid, dists, grid, starti, startj, endi, endj)) {
                l = mid;
            } else {
                r = mid - 1;
            }
        }
        return l;
    }

    public static boolean works(int mid, int[][] dists, int[][] grid, int starti, int startj, int endi, int endj) {
        Queue<Node> q = new LinkedList<>();
        q.add(new Node(starti, startj, (long) mid * S - 1));
        boolean[][] visited = new boolean[grid.length][grid[0].length];
        while (!q.isEmpty()) {
            Node p = q.poll();
            if (p.i == endi && p.j == endj) {
                return true;
            }
            if (visited[p.i][p.j]) {
                continue;
            }
            visited[p.i][p.j] = true;
            for (int i = 0; i < 4; i++) {
                int newi = dx[i] + p.i;
                int newj = dy[i] + p.j;
                if (inRange(newi, newj, grid)) {
                    if (grid[newi][newj] != 2 && dists[newi][newj] > (p.dist + 1) / S || newi == endi && newj == endj && dists[newi][newj] == (p.dist + 1) / S) {
                        q.add(new Node(newi, newj, p.dist + 1));
                    }
                }
            }
        }
        return false;
    }

    public static boolean inRange(int i, int j, int[][] grid) {
        return i >= 0 && j >= 0 && i < grid.length && j < grid[0].length;
    }

    static class Node {
        int i, j;
        long dist;

        public Node(int a, int b, long c) {
            i = a;
            j = b;
            dist = c;
        }
    }

}

Subtask #1
41.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 8460 KB Output isn't correct
2 Correct 49 ms 8216 KB Output is correct
3 Incorrect 50 ms 8332 KB Output isn't correct
4 Correct 47 ms 8368 KB Output is correct
5 Correct 56 ms 8468 KB Output is correct
6 Correct 49 ms 8548 KB Output is correct
7 Correct 585 ms 32948 KB Output is correct
8 Incorrect 49 ms 8636 KB Output isn't correct
9 Correct 50 ms 8712 KB Output is correct
10 Correct 49 ms 8504 KB Output is correct
11 Correct 50 ms 8604 KB Output is correct
12 Incorrect 57 ms 8808 KB Output isn't correct
13 Incorrect 63 ms 9164 KB Output isn't correct
14 Correct 99 ms 12544 KB Output is correct
15 Incorrect 48 ms 8632 KB Output isn't correct
16 Correct 50 ms 8504 KB Output is correct
17 Incorrect 49 ms 8492 KB Output isn't correct
18 Correct 50 ms 8604 KB Output is correct
19 Incorrect 55 ms 8604 KB Output isn't correct
20 Correct 50 ms 8616 KB Output is correct
21 Incorrect 55 ms 8364 KB Output isn't correct
22 Correct 53 ms 8480 KB Output is correct
23 Incorrect 55 ms 8740 KB Output isn't correct
24 Correct 61 ms 8828 KB Output is correct
25 Incorrect 57 ms 8684 KB Output isn't correct
26 Correct 63 ms 8944 KB Output is correct
27 Incorrect 72 ms 8824 KB Output isn't correct
28 Correct 67 ms 8996 KB Output is correct
29 Incorrect 60 ms 8852 KB Output isn't correct
30 Correct 64 ms 8952 KB Output is correct
31 Incorrect 73 ms 10436 KB Output isn't correct
32 Correct 78 ms 11204 KB Output is correct
33 Incorrect 152 ms 14820 KB Output isn't correct
34 Correct 218 ms 14844 KB Output is correct
35 Correct 265 ms 16276 KB Output is correct
36 Incorrect 147 ms 15056 KB Output isn't correct
37 Correct 206 ms 15508 KB Output is correct
38 Correct 291 ms 16588 KB Output is correct
39 Incorrect 149 ms 15956 KB Output isn't correct
40 Correct 209 ms 15876 KB Output is correct
41 Correct 315 ms 17588 KB Output is correct
42 Incorrect 158 ms 16000 KB Output isn't correct
43 Correct 215 ms 16184 KB Output is correct
44 Correct 365 ms 18572 KB Output is correct
45 Incorrect 154 ms 16520 KB Output isn't correct
46 Correct 209 ms 16448 KB Output is correct
47 Correct 397 ms 19228 KB Output is correct
48 Incorrect 155 ms 16832 KB Output isn't correct
49 Correct 214 ms 17128 KB Output is correct
50 Correct 410 ms 19820 KB Output is correct
51 Incorrect 155 ms 17488 KB Output isn't correct
52 Correct 217 ms 18008 KB Output is correct
53 Correct 456 ms 21212 KB Output is correct
54 Incorrect 157 ms 18136 KB Output isn't correct
55 Correct 224 ms 18836 KB Output is correct
56 Correct 478 ms 23352 KB Output is correct
57 Incorrect 168 ms 18792 KB Output isn't correct
58 Correct 235 ms 21040 KB Output is correct
59 Correct 551 ms 25632 KB Output is correct
60 Incorrect 173 ms 20492 KB Output isn't correct
61 Correct 240 ms 21688 KB Output is correct
62 Correct 603 ms 25868 KB Output is correct
63 Correct 377 ms 25724 KB Output is correct
64 Correct 592 ms 26564 KB Output is correct
65 Correct 496 ms 26372 KB Output is correct
66 Incorrect 448 ms 26264 KB Output isn't correct
67 Correct 417 ms 25820 KB Output is correct
68 Correct 297 ms 25256 KB Output is correct
69 Correct 296 ms 24764 KB Output is correct
70 Correct 294 ms 23444 KB Output is correct
71 Correct 277 ms 24656 KB Output is correct
72 Incorrect 270 ms 21792 KB Output isn't correct
73 Incorrect 430 ms 47700 KB Output isn't correct
74 Correct 503 ms 47672 KB Output is correct
75 Correct 541 ms 47704 KB Output is correct
76 Correct 538 ms 47924 KB Output is correct
77 Correct 518 ms 47692 KB Output is correct
78 Correct 585 ms 44364 KB Output is correct
79 Correct 483 ms 44504 KB Output is correct
80 Correct 484 ms 44656 KB Output is correct
81 Correct 542 ms 44684 KB Output is correct
82 Correct 538 ms 44496 KB Output is correct
83 Correct 593 ms 40492 KB Output is correct
84 Correct 550 ms 40640 KB Output is correct
85 Correct 570 ms 40620 KB Output is correct
86 Correct 565 ms 40588 KB Output is correct
87 Correct 563 ms 40672 KB Output is correct
88 Correct 618 ms 36808 KB Output is correct
89 Correct 599 ms 36704 KB Output is correct
90 Correct 661 ms 36708 KB Output is correct
91 Correct 589 ms 36828 KB Output is correct
92 Correct 649 ms 36768 KB Output is correct