oj.uz

Submission #581658

# Submission time Handle Problem Language Result Execution time Memory
581658 2022-06-23T01:41:56 Z DylanSmith Tracks in the Snow (BOI13_tracks) Java 11
89.0625 / 100
 2000 ms 412220 KB 
import java.util.*;
import java.io.*;
public class tracks {
    public static void main(String[] args) throws IOException {
        Reader in = new Reader();
        PrintWriter out = new PrintWriter(System.out);
        
        int N = in.nextInt(), M = in.nextInt();
        char[][] mat = new char[N][M];
        for (int i = 0; i < N; i++) {
            mat[i] = in.next().toCharArray();
        }
        int[][] dist = new int[N][M];
        for (int i = 0; i < N; i++) {
            Arrays.fill(dist[i], -1);
        }
        dist[0][0] = 0;
        Deque<Integer> q = new LinkedList<>();
        q.offer(0);
        int[] x = new int[]{-1, 1, 0, 0}, y = new int[]{0, 0, -1, 1};
        int res = 0;
        while (!q.isEmpty()) {
            int current = q.poll();
            int r = current / M, c = current % M;
            res = Math.max(res, dist[r][c]);
            for (int k = 0; k < 4; k++) {
                int r2 = r + x[k], c2 = c + y[k];
                if (r2 >= 0 && r2 < N && c2 >= 0 && c2 < M) {
                    if (mat[r2][c2] != '.' && dist[r2][c2] == -1) {
                        if (mat[r2][c2] == mat[r][c]) {
                            dist[r2][c2] = dist[r][c];
                            q.addFirst(r2 * M + c2);
                        } else {
                            dist[r2][c2] = dist[r][c] + 1;
                            q.offer(r2 * M + c2);
                        }
                    }
                }
            }
        }
        out.println(res + 1);
        
        out.close();
    }
    static class Reader {
        BufferedInputStream in;
        public Reader() {
            in = new BufferedInputStream(System.in);
        }
        public String nextLine() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public String next() throws IOException {
            int c;
            StringBuilder sb = new StringBuilder("");
            while ((c = in.read()) != ' ' && c != '\n')
                sb.append((char)(c));
            return sb.toString();
        }
        public int nextInt() throws IOException {
            return (int)nextLong();
        }
        public long nextLong() throws IOException {
            int c;
            long res = 0;
            boolean start = false, negative = false;
            while ((c = in.read()) != ' ' && c != '\n' || !start)
                if (c >= '0' && c <= '9' || c == '-') {
                    start = true;
                    if (c == '-')
                        negative = true;
                    else
                        res = res * 10 + c - '0';
                }
            return res * (negative ? -1 : 1);
        }
    }
    public static void sort(int[] arr) {
        List<Integer> list = new ArrayList<>();
        for (int i : arr) {
            list.add(i);
        }
        Collections.sort(list);
        for (int i = 0; i < arr.length; i++) {
            arr[i] = list.get(i);
        }
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 181 ms 14724 KB Output is correct
2 Correct 66 ms 8296 KB Output is correct
3 Correct 68 ms 8564 KB Output is correct
4 Correct 221 ms 14652 KB Output is correct
5 Correct 135 ms 12884 KB Output is correct
6 Correct 68 ms 8392 KB Output is correct
7 Correct 86 ms 8256 KB Output is correct
8 Correct 90 ms 10356 KB Output is correct
9 Correct 102 ms 9304 KB Output is correct
10 Correct 167 ms 12512 KB Output is correct
11 Correct 183 ms 13404 KB Output is correct
12 Correct 143 ms 13164 KB Output is correct
13 Correct 133 ms 12728 KB Output is correct
14 Correct 153 ms 12664 KB Output is correct
15 Correct 182 ms 14644 KB Output is correct
16 Correct 170 ms 14660 KB Output is correct
17 Correct 164 ms 14468 KB Output is correct
18 Correct 220 ms 14868 KB Output is correct

Subtask #2
59.0625 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 12644 KB Output is correct
2 Correct 309 ms 25172 KB Output is correct
3 Correct 779 ms 169392 KB Output is correct
4 Correct 309 ms 43328 KB Output is correct
5 Correct 614 ms 99680 KB Output is correct
6 Execution timed out 2096 ms 309160 KB Time limit exceeded
7 Correct 143 ms 12572 KB Output is correct
8 Correct 137 ms 12712 KB Output is correct
9 Correct 203 ms 12896 KB Output is correct
10 Correct 164 ms 10972 KB Output is correct
11 Correct 134 ms 11628 KB Output is correct
12 Correct 134 ms 10792 KB Output is correct
13 Correct 274 ms 25476 KB Output is correct
14 Correct 205 ms 20940 KB Output is correct
15 Correct 202 ms 20232 KB Output is correct
16 Correct 179 ms 17728 KB Output is correct
17 Correct 408 ms 51484 KB Output is correct
18 Correct 337 ms 50036 KB Output is correct
19 Correct 324 ms 43396 KB Output is correct
20 Correct 300 ms 41540 KB Output is correct
21 Correct 570 ms 103608 KB Output is correct
22 Correct 606 ms 99516 KB Output is correct
23 Correct 628 ms 86916 KB Output is correct
24 Correct 585 ms 101388 KB Output is correct
25 Correct 1098 ms 169328 KB Output is correct
26 Execution timed out 2102 ms 412220 KB Time limit exceeded
27 Correct 1730 ms 262124 KB Output is correct
28 Execution timed out 2097 ms 309292 KB Time limit exceeded
29 Execution timed out 2096 ms 293472 KB Time limit exceeded
30 Execution timed out 2098 ms 331716 KB Time limit exceeded
31 Correct 1279 ms 118216 KB Output is correct
32 Correct 1720 ms 281072 KB Output is correct