oj.uz

Submission #920842

# Submission time Handle Problem Language Result Execution time Memory
920842 2024-02-03T05:51:59 Z sushikid Tracks in the Snow (BOI13_tracks) Java 11
97.8125 / 100
 2000 ms 603532 KB 
import java.util.*;
import java.io.*;

public class tracks {
    private static int[] dx = {-1, 0, 1, 0};
    private static int[] dy = {0, -1, 0, 1};
    public static void main(String[] args) throws IOException{
        BufferedReader r = new BufferedReader(new InputStreamReader(System.in));
        PrintWriter pw = new PrintWriter(System.out);
        StringTokenizer st = new StringTokenizer(r.readLine());
        int h = Integer.parseInt(st.nextToken()); int w = Integer.parseInt(st.nextToken());
        int[][] grid = new int[h][w];
        int[][] dist = new int[h][w];
        for (int i = 0; i < h; i++) {
            String s = r.readLine();
            for (int j = 0; j < w; j++) {
                dist[i][j] = Integer.MAX_VALUE;
                if(s.charAt(j) == 'F'){
                    grid[i][j] = 0;
                }
                else if(s.charAt(j) == 'R'){
                    grid[i][j] = 1;
                }
                else{
                    grid[i][j] = 2;
                }
            }
        }
        dist[0][0] = 1;
        LinkedList<int[]> cur = new LinkedList<>();
        cur.add(new int[]{0, 0});
        while(!cur.isEmpty()){
            int[] x = cur.poll();
            for (int i = 0; i < 4; i++) {
                int fx = x[0] + dx[i];
                int fy = x[1] + dy[i];
                if(0 <= fx && fx < h && 0 <= fy && fy < w && grid[fx][fy] != 2){
                    if(grid[fx][fy] == grid[x[0]][x[1]]){
                        if(dist[x[0]][x[1]] < dist[fx][fy]){
                            dist[fx][fy] = dist[x[0]][x[1]];
                            cur.addFirst(new int[]{fx, fy});
                        }
                    }
                    else{
                        if(dist[x[0]][x[1]] + 1 < dist[fx][fy]){
                            dist[fx][fy] = dist[x[0]][x[1]] + 1;
                            cur.addLast(new int[]{fx, fy});
                        }
                    }
                }
            }
        }
        int max = Integer.MIN_VALUE;
        for(int[] e1 : dist){
            for(int e2 : e1){
                if(e2 != Integer.MAX_VALUE){
                    max = Math.max(max, e2);
                }
            }
        }
        pw.println(max);
        pw.close();
    }
}

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 174 ms 33524 KB Output is correct
2 Correct 56 ms 21888 KB Output is correct
3 Correct 58 ms 22576 KB Output is correct
4 Correct 149 ms 29620 KB Output is correct
5 Correct 131 ms 26604 KB Output is correct
6 Correct 54 ms 22520 KB Output is correct
7 Correct 62 ms 26640 KB Output is correct
8 Correct 72 ms 24732 KB Output is correct
9 Correct 74 ms 23708 KB Output is correct
10 Correct 139 ms 28528 KB Output is correct
11 Correct 146 ms 30620 KB Output is correct
12 Correct 142 ms 31308 KB Output is correct
13 Correct 138 ms 26556 KB Output is correct
14 Correct 138 ms 26380 KB Output is correct
15 Correct 173 ms 29828 KB Output is correct
16 Correct 161 ms 31404 KB Output is correct
17 Correct 152 ms 29452 KB Output is correct
18 Correct 156 ms 29196 KB Output is correct

Subtask #2
67.8125 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 137 ms 26396 KB Output is correct
2 Correct 243 ms 47308 KB Output is correct
3 Correct 667 ms 255644 KB Output is correct
4 Correct 273 ms 79108 KB Output is correct
5 Correct 490 ms 154304 KB Output is correct
6 Execution timed out 2044 ms 410104 KB Time limit exceeded
7 Correct 159 ms 25676 KB Output is correct
8 Correct 131 ms 26900 KB Output is correct
9 Correct 182 ms 26032 KB Output is correct
10 Correct 153 ms 25200 KB Output is correct
11 Correct 131 ms 29444 KB Output is correct
12 Correct 123 ms 25044 KB Output is correct
13 Correct 219 ms 47496 KB Output is correct
14 Correct 180 ms 38780 KB Output is correct
15 Correct 173 ms 38180 KB Output is correct
16 Correct 174 ms 35464 KB Output is correct
17 Correct 346 ms 86492 KB Output is correct
18 Correct 314 ms 82840 KB Output is correct
19 Correct 288 ms 78660 KB Output is correct
20 Correct 251 ms 78976 KB Output is correct
21 Correct 453 ms 161008 KB Output is correct
22 Correct 492 ms 154300 KB Output is correct
23 Correct 552 ms 138860 KB Output is correct
24 Correct 473 ms 155084 KB Output is correct
25 Correct 963 ms 258140 KB Output is correct
26 Correct 1648 ms 603532 KB Output is correct
27 Correct 1646 ms 484396 KB Output is correct
28 Correct 1929 ms 410428 KB Output is correct
29 Correct 1856 ms 399116 KB Output is correct
30 Correct 1840 ms 449044 KB Output is correct
31 Correct 1168 ms 175396 KB Output is correct
32 Correct 1375 ms 467700 KB Output is correct