| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 815879 |
2023-08-09T01:58:03 Z |
powervic08 |
Mecho (IOI09_mecho) |
Java 11 |
|
562 ms |
47872 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));
}
}
}
}
dists[endi][endj] = Integer.MAX_VALUE;
int l = -1;
int r = 2 * n * n;
while (r - l > 1) {
int mid = (l + r) / 2;
if (works(mid, dists, grid, starti, startj, endi, endj)) {
l = mid;
} else {
r = mid;
}
}
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 && !visited[newi][newj]) {
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;
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
51 ms |
8184 KB |
Output is correct |
| 2 |
Correct |
48 ms |
8316 KB |
Output is correct |
| 3 |
Correct |
49 ms |
8376 KB |
Output is correct |
| 4 |
Correct |
49 ms |
8292 KB |
Output is correct |
| 5 |
Correct |
49 ms |
8496 KB |
Output is correct |
| 6 |
Correct |
55 ms |
8292 KB |
Output is correct |
| 7 |
Correct |
493 ms |
33292 KB |
Output is correct |
| 8 |
Correct |
50 ms |
8416 KB |
Output is correct |
| 9 |
Correct |
49 ms |
8568 KB |
Output is correct |
| 10 |
Correct |
51 ms |
8572 KB |
Output is correct |
| 11 |
Correct |
50 ms |
8280 KB |
Output is correct |
| 12 |
Incorrect |
58 ms |
8732 KB |
Output isn't correct |
| 13 |
Incorrect |
61 ms |
8908 KB |
Output isn't correct |
| 14 |
Correct |
108 ms |
11508 KB |
Output is correct |
| 15 |
Correct |
52 ms |
8544 KB |
Output is correct |
| 16 |
Correct |
48 ms |
8348 KB |
Output is correct |
| 17 |
Correct |
54 ms |
8408 KB |
Output is correct |
| 18 |
Correct |
49 ms |
8608 KB |
Output is correct |
| 19 |
Correct |
53 ms |
8244 KB |
Output is correct |
| 20 |
Correct |
50 ms |
8620 KB |
Output is correct |
| 21 |
Correct |
52 ms |
8468 KB |
Output is correct |
| 22 |
Correct |
53 ms |
8796 KB |
Output is correct |
| 23 |
Correct |
54 ms |
8672 KB |
Output is correct |
| 24 |
Correct |
58 ms |
8768 KB |
Output is correct |
| 25 |
Correct |
57 ms |
8932 KB |
Output is correct |
| 26 |
Correct |
62 ms |
8828 KB |
Output is correct |
| 27 |
Correct |
60 ms |
8936 KB |
Output is correct |
| 28 |
Correct |
61 ms |
8776 KB |
Output is correct |
| 29 |
Correct |
62 ms |
8764 KB |
Output is correct |
| 30 |
Correct |
61 ms |
8896 KB |
Output is correct |
| 31 |
Correct |
75 ms |
10392 KB |
Output is correct |
| 32 |
Correct |
65 ms |
8976 KB |
Output is correct |
| 33 |
Correct |
145 ms |
15028 KB |
Output is correct |
| 34 |
Correct |
202 ms |
14912 KB |
Output is correct |
| 35 |
Correct |
255 ms |
16112 KB |
Output is correct |
| 36 |
Correct |
142 ms |
15344 KB |
Output is correct |
| 37 |
Correct |
218 ms |
15264 KB |
Output is correct |
| 38 |
Correct |
262 ms |
16764 KB |
Output is correct |
| 39 |
Correct |
163 ms |
15744 KB |
Output is correct |
| 40 |
Correct |
206 ms |
15912 KB |
Output is correct |
| 41 |
Correct |
285 ms |
17668 KB |
Output is correct |
| 42 |
Correct |
153 ms |
16016 KB |
Output is correct |
| 43 |
Correct |
212 ms |
16200 KB |
Output is correct |
| 44 |
Correct |
310 ms |
18764 KB |
Output is correct |
| 45 |
Correct |
154 ms |
16448 KB |
Output is correct |
| 46 |
Correct |
206 ms |
16440 KB |
Output is correct |
| 47 |
Correct |
350 ms |
18904 KB |
Output is correct |
| 48 |
Correct |
161 ms |
16828 KB |
Output is correct |
| 49 |
Correct |
219 ms |
17308 KB |
Output is correct |
| 50 |
Correct |
359 ms |
19884 KB |
Output is correct |
| 51 |
Correct |
159 ms |
17580 KB |
Output is correct |
| 52 |
Correct |
220 ms |
17532 KB |
Output is correct |
| 53 |
Correct |
401 ms |
20948 KB |
Output is correct |
| 54 |
Correct |
163 ms |
18112 KB |
Output is correct |
| 55 |
Correct |
238 ms |
18636 KB |
Output is correct |
| 56 |
Correct |
438 ms |
23116 KB |
Output is correct |
| 57 |
Correct |
171 ms |
19072 KB |
Output is correct |
| 58 |
Correct |
245 ms |
18660 KB |
Output is correct |
| 59 |
Correct |
472 ms |
25240 KB |
Output is correct |
| 60 |
Correct |
206 ms |
20500 KB |
Output is correct |
| 61 |
Correct |
234 ms |
21368 KB |
Output is correct |
| 62 |
Correct |
507 ms |
25456 KB |
Output is correct |
| 63 |
Correct |
400 ms |
25960 KB |
Output is correct |
| 64 |
Correct |
562 ms |
26700 KB |
Output is correct |
| 65 |
Correct |
471 ms |
26076 KB |
Output is correct |
| 66 |
Correct |
424 ms |
26100 KB |
Output is correct |
| 67 |
Correct |
393 ms |
25672 KB |
Output is correct |
| 68 |
Correct |
292 ms |
23696 KB |
Output is correct |
| 69 |
Correct |
316 ms |
23972 KB |
Output is correct |
| 70 |
Correct |
285 ms |
22128 KB |
Output is correct |
| 71 |
Correct |
336 ms |
22236 KB |
Output is correct |
| 72 |
Incorrect |
252 ms |
21428 KB |
Output isn't correct |
| 73 |
Incorrect |
483 ms |
47604 KB |
Output isn't correct |
| 74 |
Correct |
547 ms |
47608 KB |
Output is correct |
| 75 |
Correct |
535 ms |
47716 KB |
Output is correct |
| 76 |
Correct |
528 ms |
47872 KB |
Output is correct |
| 77 |
Correct |
536 ms |
47588 KB |
Output is correct |
| 78 |
Correct |
518 ms |
44604 KB |
Output is correct |
| 79 |
Correct |
462 ms |
44504 KB |
Output is correct |
| 80 |
Correct |
439 ms |
44668 KB |
Output is correct |
| 81 |
Correct |
516 ms |
44768 KB |
Output is correct |
| 82 |
Correct |
475 ms |
44780 KB |
Output is correct |
| 83 |
Correct |
518 ms |
40536 KB |
Output is correct |
| 84 |
Correct |
497 ms |
40668 KB |
Output is correct |
| 85 |
Correct |
507 ms |
40440 KB |
Output is correct |
| 86 |
Correct |
495 ms |
40592 KB |
Output is correct |
| 87 |
Correct |
523 ms |
40408 KB |
Output is correct |
| 88 |
Correct |
498 ms |
36748 KB |
Output is correct |
| 89 |
Correct |
521 ms |
36636 KB |
Output is correct |
| 90 |
Correct |
526 ms |
36644 KB |
Output is correct |
| 91 |
Correct |
541 ms |
36640 KB |
Output is correct |
| 92 |
Correct |
526 ms |
36800 KB |
Output is correct |
