oj.uz

Submission #815853

# Submission time Handle Problem Language Result Execution time Memory
815853 2023-08-09T01:18:51 Z powervic08 Mecho (IOI09_mecho) Java 11
41 / 100
 700 ms 47800 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));
        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) / S || newi == endi && newj == endj && dists[newi][newj] == (p.dist) / 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 50 ms 8528 KB Output isn't correct
2 Correct 47 ms 8432 KB Output is correct
3 Incorrect 46 ms 8540 KB Output isn't correct
4 Correct 48 ms 8272 KB Output is correct
5 Correct 49 ms 8328 KB Output is correct
6 Correct 52 ms 8232 KB Output is correct
7 Correct 604 ms 32988 KB Output is correct
8 Incorrect 58 ms 8344 KB Output isn't correct
9 Correct 60 ms 8228 KB Output is correct
10 Correct 54 ms 8468 KB Output is correct
11 Correct 58 ms 8448 KB Output is correct
12 Incorrect 58 ms 8796 KB Output isn't correct
13 Incorrect 67 ms 9056 KB Output isn't correct
14 Correct 99 ms 12532 KB Output is correct
15 Incorrect 50 ms 8392 KB Output isn't correct
16 Correct 51 ms 8440 KB Output is correct
17 Incorrect 54 ms 8296 KB Output isn't correct
18 Correct 61 ms 8432 KB Output is correct
19 Incorrect 52 ms 8664 KB Output isn't correct
20 Correct 51 ms 8712 KB Output is correct
21 Incorrect 52 ms 8668 KB Output isn't correct
22 Correct 54 ms 8740 KB Output is correct
23 Incorrect 56 ms 8704 KB Output isn't correct
24 Correct 55 ms 8832 KB Output is correct
25 Incorrect 60 ms 8732 KB Output isn't correct
26 Correct 64 ms 8824 KB Output is correct
27 Incorrect 62 ms 8708 KB Output isn't correct
28 Correct 62 ms 9056 KB Output is correct
29 Incorrect 60 ms 8840 KB Output isn't correct
30 Correct 63 ms 8852 KB Output is correct
31 Incorrect 69 ms 10132 KB Output isn't correct
32 Correct 84 ms 11184 KB Output is correct
33 Incorrect 160 ms 14732 KB Output isn't correct
34 Correct 198 ms 15040 KB Output is correct
35 Correct 258 ms 16128 KB Output is correct
36 Incorrect 145 ms 15340 KB Output isn't correct
37 Correct 213 ms 15448 KB Output is correct
38 Correct 269 ms 17136 KB Output is correct
39 Incorrect 148 ms 15696 KB Output isn't correct
40 Correct 236 ms 15836 KB Output is correct
41 Correct 315 ms 17916 KB Output is correct
42 Incorrect 158 ms 16144 KB Output isn't correct
43 Correct 217 ms 16248 KB Output is correct
44 Correct 338 ms 18792 KB Output is correct
45 Incorrect 153 ms 16620 KB Output isn't correct
46 Correct 220 ms 16504 KB Output is correct
47 Correct 371 ms 19232 KB Output is correct
48 Incorrect 158 ms 16880 KB Output isn't correct
49 Correct 226 ms 17328 KB Output is correct
50 Correct 410 ms 19868 KB Output is correct
51 Incorrect 157 ms 17732 KB Output isn't correct
52 Correct 233 ms 17932 KB Output is correct
53 Correct 456 ms 21352 KB Output is correct
54 Incorrect 165 ms 18188 KB Output isn't correct
55 Correct 226 ms 18812 KB Output is correct
56 Correct 494 ms 23388 KB Output is correct
57 Incorrect 170 ms 18956 KB Output isn't correct
58 Correct 236 ms 21352 KB Output is correct
59 Correct 530 ms 25564 KB Output is correct
60 Incorrect 175 ms 20528 KB Output isn't correct
61 Correct 244 ms 21684 KB Output is correct
62 Correct 566 ms 25868 KB Output is correct
63 Correct 385 ms 25684 KB Output is correct
64 Correct 617 ms 26620 KB Output is correct
65 Correct 496 ms 26312 KB Output is correct
66 Incorrect 460 ms 26012 KB Output isn't correct
67 Correct 421 ms 26056 KB Output is correct
68 Correct 289 ms 25144 KB Output is correct
69 Correct 294 ms 24968 KB Output is correct
70 Correct 270 ms 23492 KB Output is correct
71 Correct 279 ms 24684 KB Output is correct
72 Incorrect 274 ms 22088 KB Output isn't correct
73 Incorrect 431 ms 47628 KB Output isn't correct
74 Correct 515 ms 47700 KB Output is correct
75 Correct 568 ms 47800 KB Output is correct
76 Correct 542 ms 47716 KB Output is correct
77 Correct 561 ms 47700 KB Output is correct
78 Correct 581 ms 44628 KB Output is correct
79 Correct 506 ms 44504 KB Output is correct
80 Correct 494 ms 44564 KB Output is correct
81 Correct 550 ms 44596 KB Output is correct
82 Correct 522 ms 44412 KB Output is correct
83 Correct 596 ms 40480 KB Output is correct
84 Correct 550 ms 40584 KB Output is correct
85 Correct 592 ms 40576 KB Output is correct
86 Correct 554 ms 40480 KB Output is correct
87 Correct 579 ms 40492 KB Output is correct
88 Correct 591 ms 36872 KB Output is correct
89 Correct 600 ms 36776 KB Output is correct
90 Correct 635 ms 36612 KB Output is correct
91 Correct 608 ms 36832 KB Output is correct
92 Correct 700 ms 36820 KB Output is correct