Submission #666560

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
666560	2022-11-29T03:10:55 Z	achejakhang	Tracks in the Snow (BOI13_tracks)	Java 11	86.875 / 100	2000 ms	656992 KB

tracks

import java.util.*;
import java.io.*;

public class tracks {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter out = new PrintWriter(System.out);
		
		StringTokenizer in = new StringTokenizer(br.readLine());
		int h = Integer.parseInt(in.nextToken()), w = Integer.parseInt(in.nextToken());
		int[][] grid = new int[h][w];
		for (int i=0; i< h; i++) {
			String s = br.readLine();
			for (int j =0; j< w; j++) grid[i][j] = s.charAt(j);
		}
		
		ArrayDeque<int[]> next = new ArrayDeque<>();
		next.addLast(new int[] {0,0,1});
		int maxV = 1;
		while (!next.isEmpty()) {
			int[] vals = next.removeFirst();
			int r = vals[0], c = vals[1], v = vals[2];
			maxV = Math.max(maxV, v);
			if (r < h-1 && grid[r+1][c] != '.') {
				if (grid[r+1][c]==grid[r][c]) {
					next.addFirst(new int[] {r+1,c,v});
				} else {
					next.addLast(new int[] {r+1,c,v+1});
				}
			}
			if (r > 0 && grid[r-1][c] != '.') {
				if (grid[r-1][c]==grid[r][c]) {
					next.addFirst(new int[] {r-1,c,v});
				} else {
					next.addLast(new int[] {r-1,c,v+1});
				}
			}
			if (c < w-1 && grid[r][c+1] != '.') {
				if (grid[r][c+1]==grid[r][c]) {
					next.addFirst(new int[] {r,c+1,v});
				} else {
					next.addLast(new int[] {r,c+1,v+1});
				}
			}
			if (c > 0 && grid[r][c-1] != '.') {
				if (grid[r][c-1]==grid[r][c]) {
					next.addFirst(new int[] {r,c-1,v});
				} else {
					next.addLast(new int[] {r,c-1,v+1});
				}
			}
			grid[r][c] = '.';
		}
		out.println(maxV);
		br.close();
		out.close();
	}
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	285 ms	18416 KB	Output is correct
2	Correct	77 ms	8288 KB	Output is correct
3	Correct	66 ms	8360 KB	Output is correct
4	Correct	381 ms	19172 KB	Output is correct
5	Correct	210 ms	13192 KB	Output is correct
6	Correct	56 ms	8296 KB	Output is correct
7	Correct	65 ms	8572 KB	Output is correct
8	Correct	85 ms	8852 KB	Output is correct
9	Correct	88 ms	10016 KB	Output is correct
10	Correct	267 ms	15532 KB	Output is correct
11	Correct	280 ms	16032 KB	Output is correct
12	Correct	235 ms	16516 KB	Output is correct
13	Correct	187 ms	13416 KB	Output is correct
14	Correct	190 ms	13292 KB	Output is correct
15	Correct	263 ms	16752 KB	Output is correct
16	Correct	296 ms	18676 KB	Output is correct
17	Correct	285 ms	16796 KB	Output is correct
18	Correct	376 ms	19228 KB	Output is correct

Subtask #2

56.875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	193 ms	13172 KB	Output is correct
2	Correct	326 ms	25420 KB	Output is correct
3	Correct	740 ms	122932 KB	Output is correct
4	Correct	289 ms	40948 KB	Output is correct
5	Correct	466 ms	73412 KB	Output is correct
6	Execution timed out	2079 ms	438540 KB	Time limit exceeded
7	Correct	226 ms	12940 KB	Output is correct
8	Correct	208 ms	12984 KB	Output is correct
9	Correct	223 ms	14728 KB	Output is correct
10	Correct	178 ms	11852 KB	Output is correct
11	Correct	159 ms	11908 KB	Output is correct
12	Correct	176 ms	12460 KB	Output is correct
13	Correct	307 ms	25452 KB	Output is correct
14	Correct	272 ms	19872 KB	Output is correct
15	Correct	207 ms	19492 KB	Output is correct
16	Correct	283 ms	18728 KB	Output is correct
17	Correct	429 ms	42784 KB	Output is correct
18	Correct	276 ms	40828 KB	Output is correct
19	Correct	303 ms	40732 KB	Output is correct
20	Correct	295 ms	38948 KB	Output is correct
21	Correct	500 ms	76432 KB	Output is correct
22	Correct	458 ms	74072 KB	Output is correct
23	Correct	655 ms	68568 KB	Output is correct
24	Correct	399 ms	74332 KB	Output is correct
25	Correct	750 ms	121660 KB	Output is correct
26	Execution timed out	2071 ms	656992 KB	Time limit exceeded
27	Execution timed out	2085 ms	424068 KB	Time limit exceeded
28	Execution timed out	2031 ms	435128 KB	Time limit exceeded
29	Execution timed out	2059 ms	380064 KB	Time limit exceeded
30	Execution timed out	2103 ms	446348 KB	Time limit exceeded
31	Correct	1774 ms	105388 KB	Output is correct
32	Correct	1795 ms	390576 KB	Output is correct