oj.uz

Submission #581657

# Submission time Handle Problem Language Result Execution time Memory
581657 2022-06-23T01:38:32 Z DylanSmith Tracks in the Snow (BOI13_tracks) Java 11
86.875 / 100
 2000 ms 544828 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<int[]> q = new LinkedList<>();
        q.offer(new int[]{0, 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[0], c = current[1];
            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(new int[]{r2, c2});
                        } else {
                            dist[r2][c2] = dist[r][c] + 1;
                            q.offer(new int[]{r2, 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 156 ms 15128 KB Output is correct
2 Correct 61 ms 8420 KB Output is correct
3 Correct 69 ms 8452 KB Output is correct
4 Correct 211 ms 15256 KB Output is correct
5 Correct 138 ms 12332 KB Output is correct
6 Correct 62 ms 8412 KB Output is correct
7 Correct 63 ms 8268 KB Output is correct
8 Correct 89 ms 10192 KB Output is correct
9 Correct 118 ms 9372 KB Output is correct
10 Correct 152 ms 12616 KB Output is correct
11 Correct 160 ms 13012 KB Output is correct
12 Correct 158 ms 13192 KB Output is correct
13 Correct 144 ms 12372 KB Output is correct
14 Correct 134 ms 12648 KB Output is correct
15 Correct 174 ms 14640 KB Output is correct
16 Correct 175 ms 14852 KB Output is correct
17 Correct 156 ms 14452 KB Output is correct
18 Correct 185 ms 15116 KB Output is correct

Subtask #2
56.875 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 135 ms 12644 KB Output is correct
2 Correct 271 ms 25396 KB Output is correct
3 Correct 783 ms 169624 KB Output is correct
4 Correct 317 ms 43504 KB Output is correct
5 Correct 643 ms 99824 KB Output is correct
6 Execution timed out 2037 ms 334200 KB Time limit exceeded
7 Correct 148 ms 12324 KB Output is correct
8 Correct 140 ms 12656 KB Output is correct
9 Correct 196 ms 12872 KB Output is correct
10 Correct 159 ms 11156 KB Output is correct
11 Correct 128 ms 11472 KB Output is correct
12 Correct 132 ms 10796 KB Output is correct
13 Correct 272 ms 25176 KB Output is correct
14 Correct 203 ms 20836 KB Output is correct
15 Correct 203 ms 20536 KB Output is correct
16 Correct 188 ms 17920 KB Output is correct
17 Correct 418 ms 51288 KB Output is correct
18 Correct 358 ms 50020 KB Output is correct
19 Correct 337 ms 43216 KB Output is correct
20 Correct 301 ms 41424 KB Output is correct
21 Correct 557 ms 103444 KB Output is correct
22 Correct 632 ms 99652 KB Output is correct
23 Correct 647 ms 87088 KB Output is correct
24 Correct 577 ms 101480 KB Output is correct
25 Correct 1047 ms 169480 KB Output is correct
26 Execution timed out 2083 ms 544828 KB Time limit exceeded
27 Execution timed out 2101 ms 357880 KB Time limit exceeded
28 Execution timed out 2067 ms 366932 KB Time limit exceeded
29 Execution timed out 2081 ms 338984 KB Time limit exceeded
30 Execution timed out 2088 ms 358868 KB Time limit exceeded
31 Correct 1354 ms 119108 KB Output is correct
32 Correct 1719 ms 307240 KB Output is correct