oj.uz

Submission #815872

# Submission time Handle Problem Language Result Execution time Memory
815872 2023-08-09T01:50:13 Z powervic08 Mecho (IOI09_mecho) Java 11
4 / 100
 824 ms 47780 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] == 0) {
                        q.add(new Node(newi, newj, p.dist + S));
                    }
                }
            }
        }
        grid[endi][endj] = Integer.MAX_VALUE;
        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] == 0 && dists[newi][newj] > p.dist + 1 || newi == endi && newj == endj && dists[newi][newj] == p.dist + 1) {
                        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
4.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 49 ms 8372 KB Output isn't correct
2 Incorrect 47 ms 8492 KB Output isn't correct
3 Incorrect 61 ms 8252 KB Output isn't correct
4 Incorrect 64 ms 8464 KB Output isn't correct
5 Incorrect 51 ms 8356 KB Output isn't correct
6 Incorrect 64 ms 8400 KB Output isn't correct
7 Incorrect 694 ms 33212 KB Output isn't correct
8 Correct 65 ms 8440 KB Output is correct
9 Incorrect 68 ms 8312 KB Output isn't correct
10 Incorrect 60 ms 8364 KB Output isn't correct
11 Incorrect 51 ms 8548 KB Output isn't correct
12 Incorrect 57 ms 8720 KB Output isn't correct
13 Incorrect 82 ms 9180 KB Output isn't correct
14 Correct 128 ms 12424 KB Output is correct
15 Incorrect 78 ms 8360 KB Output isn't correct
16 Incorrect 56 ms 8268 KB Output isn't correct
17 Incorrect 59 ms 8332 KB Output isn't correct
18 Incorrect 54 ms 8804 KB Output isn't correct
19 Incorrect 69 ms 8644 KB Output isn't correct
20 Incorrect 85 ms 10368 KB Output isn't correct
21 Incorrect 98 ms 10680 KB Output isn't correct
22 Incorrect 91 ms 10988 KB Output isn't correct
23 Incorrect 84 ms 11056 KB Output isn't correct
24 Incorrect 102 ms 11780 KB Output isn't correct
25 Incorrect 101 ms 11664 KB Output isn't correct
26 Incorrect 103 ms 12480 KB Output isn't correct
27 Incorrect 106 ms 12416 KB Output isn't correct
28 Incorrect 109 ms 12364 KB Output isn't correct
29 Incorrect 84 ms 12376 KB Output isn't correct
30 Incorrect 98 ms 12936 KB Output isn't correct
31 Incorrect 99 ms 12608 KB Output isn't correct
32 Incorrect 134 ms 12700 KB Output isn't correct
33 Incorrect 229 ms 14756 KB Output isn't correct
34 Incorrect 268 ms 14892 KB Output isn't correct
35 Incorrect 251 ms 15804 KB Output isn't correct
36 Incorrect 248 ms 17300 KB Output isn't correct
37 Incorrect 295 ms 17820 KB Output isn't correct
38 Incorrect 341 ms 16736 KB Output isn't correct
39 Incorrect 265 ms 18840 KB Output isn't correct
40 Incorrect 311 ms 18824 KB Output isn't correct
41 Incorrect 315 ms 17268 KB Output isn't correct
42 Incorrect 263 ms 19248 KB Output isn't correct
43 Incorrect 316 ms 19072 KB Output isn't correct
44 Incorrect 398 ms 18068 KB Output isn't correct
45 Incorrect 319 ms 19372 KB Output isn't correct
46 Incorrect 345 ms 19204 KB Output isn't correct
47 Incorrect 428 ms 18896 KB Output isn't correct
48 Incorrect 293 ms 20160 KB Output isn't correct
49 Incorrect 383 ms 20636 KB Output isn't correct
50 Incorrect 421 ms 19480 KB Output isn't correct
51 Incorrect 307 ms 22272 KB Output isn't correct
52 Incorrect 406 ms 22112 KB Output isn't correct
53 Incorrect 477 ms 20644 KB Output isn't correct
54 Incorrect 367 ms 23812 KB Output isn't correct
55 Incorrect 426 ms 23796 KB Output isn't correct
56 Incorrect 456 ms 22780 KB Output isn't correct
57 Incorrect 396 ms 25800 KB Output isn't correct
58 Incorrect 483 ms 25564 KB Output isn't correct
59 Incorrect 560 ms 25120 KB Output isn't correct
60 Incorrect 379 ms 27092 KB Output isn't correct
61 Incorrect 598 ms 27020 KB Output isn't correct
62 Incorrect 655 ms 25844 KB Output isn't correct
63 Incorrect 403 ms 25604 KB Output isn't correct
64 Incorrect 625 ms 26164 KB Output isn't correct
65 Incorrect 561 ms 26236 KB Output isn't correct
66 Incorrect 498 ms 25768 KB Output isn't correct
67 Correct 411 ms 25924 KB Output is correct
68 Incorrect 297 ms 25008 KB Output isn't correct
69 Incorrect 316 ms 25016 KB Output isn't correct
70 Incorrect 309 ms 24652 KB Output isn't correct
71 Incorrect 283 ms 24060 KB Output isn't correct
72 Incorrect 344 ms 25820 KB Output isn't correct
73 Incorrect 434 ms 47592 KB Output isn't correct
74 Incorrect 750 ms 47780 KB Output isn't correct
75 Incorrect 623 ms 47684 KB Output isn't correct
76 Incorrect 580 ms 47688 KB Output isn't correct
77 Incorrect 618 ms 47596 KB Output isn't correct
78 Correct 655 ms 44380 KB Output is correct
79 Incorrect 791 ms 44616 KB Output isn't correct
80 Incorrect 591 ms 44444 KB Output isn't correct
81 Incorrect 596 ms 44436 KB Output isn't correct
82 Incorrect 628 ms 44492 KB Output isn't correct
83 Incorrect 664 ms 40268 KB Output isn't correct
84 Incorrect 824 ms 40380 KB Output isn't correct
85 Incorrect 599 ms 40428 KB Output isn't correct
86 Incorrect 628 ms 40324 KB Output isn't correct
87 Incorrect 613 ms 40448 KB Output isn't correct
88 Incorrect 598 ms 36588 KB Output isn't correct
89 Incorrect 808 ms 36596 KB Output isn't correct
90 Incorrect 680 ms 36472 KB Output isn't correct
91 Incorrect 722 ms 36524 KB Output isn't correct
92 Incorrect 657 ms 36600 KB Output isn't correct