Submission #666562

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
666562	2022-11-29T03:14:30 Z	achejakhang	Tracks in the Snow (BOI13_tracks)	Java 11	91.25 / 100	2000 ms	511700 KB

tracks

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

public class tracks {
	static final int[] dx = {0, 0, -1, 1};
	static final int[] dy = {-1, 1, 0, 0};
	static int N = 1, H, W;
	static int[][] grid, count;
	public static void main(String[] args) {
		FastIO io = new FastIO();

		H = io.nextInt();
		W = io.nextInt();
		grid = new int[H][W];

		for (int i = 0; i < H; i++) {
			String line = io.next();
			for (int j = 0; j < W; j++) {
				grid[i][j] = (line.charAt(j) == 'F')?1:(line.charAt(j) == 'R')?2:-1;
			}
		}

		io.println(bfs());
		io.close();
	}

	private static int bfs() {
		count = new int[H][W];

		LinkedList<int[]> q = new LinkedList<>();
		q.add(new int[]{0,0});
		count[0][0] = 1;

		while (!q.isEmpty()) {
			int[] curr = q.poll();

			N = Math.max(N, count[curr[0]][curr[1]]);

			for (int i = 0; i < 4; i++) {
				int nx = curr[0] + dx[i];
				int ny = curr[1] + dy[i];

				if(nx < 0 || ny < 0 || nx >= H || ny >= W) continue;
				if(count[nx][ny] > 0) continue;
				if(grid[nx][ny] == -1) continue;
				if(grid[nx][ny] != grid[curr[0]][curr[1]]) {
					count[nx][ny] = count[curr[0]][curr[1]] + 1;
					q.addLast(new int[]{nx, ny});
				}
				else {
					count[nx][ny] = count[curr[0]][curr[1]];
					q.addFirst(new int[]{nx, ny});
				}
			}
		}

		return N;
	}

	private static class FastIO extends PrintWriter {
		private InputStream stream;
		private byte[] buf = new byte[1<<16];
		private int curChar, numChars;

		// standard input
		public FastIO() { this(System.in,System.out); }
		public FastIO(InputStream i, OutputStream o) {
			super(o);
			stream = i;
		}
		// file input
		public FastIO(String i, String o) throws IOException {
			super(new FileWriter(o));
			stream = new FileInputStream(i);
		}

		// throws InputMismatchException() if previously detected end of file
		private int nextByte() {
			if (numChars == -1) throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = stream.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars == -1) return -1; // end of file
			}
			return buf[curChar++];
		}

		// to read in entire lines, replace c <= ' '
		// with a function that checks whether c is a line break
		public String next() {
			int c; do { c = nextByte(); } while (c <= ' ');
			StringBuilder res = new StringBuilder();
			do { res.appendCodePoint(c); c = nextByte(); } while (c > ' ');
			return res.toString();
		}
		public int nextInt() { // nextLong() would be implemented similarly
			int c; do { c = nextByte(); } while (c <= ' ');
			int sgn = 1; if (c == '-') { sgn = -1; c = nextByte(); }
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res = 10*res+c-'0';
				c = nextByte();
			} while (c > ' ');
			return res * sgn;
		}
		public double nextDouble() { return Double.parseDouble(next()); }
	}
}

Subtask #1

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	201 ms	14904 KB	Output is correct
2	Correct	61 ms	8476 KB	Output is correct
3	Correct	68 ms	8504 KB	Output is correct
4	Correct	229 ms	15588 KB	Output is correct
5	Correct	161 ms	13200 KB	Output is correct
6	Correct	58 ms	8524 KB	Output is correct
7	Correct	67 ms	8376 KB	Output is correct
8	Correct	85 ms	10240 KB	Output is correct
9	Correct	92 ms	9172 KB	Output is correct
10	Correct	165 ms	12896 KB	Output is correct
11	Correct	156 ms	13172 KB	Output is correct
12	Correct	161 ms	13616 KB	Output is correct
13	Correct	160 ms	12940 KB	Output is correct
14	Correct	164 ms	13192 KB	Output is correct
15	Correct	183 ms	15388 KB	Output is correct
16	Correct	203 ms	15332 KB	Output is correct
17	Correct	181 ms	14828 KB	Output is correct
18	Correct	218 ms	15484 KB	Output is correct

Subtask #2

61.25 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	148 ms	12896 KB	Output is correct
2	Correct	321 ms	31944 KB	Output is correct
3	Correct	764 ms	225884 KB	Output is correct
4	Correct	326 ms	60300 KB	Output is correct
5	Correct	537 ms	123760 KB	Output is correct
6	Execution timed out	2025 ms	377864 KB	Time limit exceeded
7	Correct	138 ms	12720 KB	Output is correct
8	Correct	138 ms	12844 KB	Output is correct
9	Correct	159 ms	12612 KB	Output is correct
10	Correct	135 ms	10996 KB	Output is correct
11	Correct	157 ms	11376 KB	Output is correct
12	Correct	126 ms	10636 KB	Output is correct
13	Correct	261 ms	31948 KB	Output is correct
14	Correct	204 ms	23676 KB	Output is correct
15	Correct	210 ms	24336 KB	Output is correct
16	Correct	201 ms	19648 KB	Output is correct
17	Correct	414 ms	64648 KB	Output is correct
18	Correct	346 ms	63844 KB	Output is correct
19	Correct	323 ms	60252 KB	Output is correct
20	Correct	303 ms	57952 KB	Output is correct
21	Correct	493 ms	127116 KB	Output is correct
22	Correct	522 ms	125296 KB	Output is correct
23	Correct	626 ms	115376 KB	Output is correct
24	Correct	517 ms	125156 KB	Output is correct
25	Correct	981 ms	226220 KB	Output is correct
26	Execution timed out	2076 ms	511700 KB	Time limit exceeded
27	Execution timed out	2079 ms	417596 KB	Time limit exceeded
28	Correct	1995 ms	374172 KB	Output is correct
29	Correct	1985 ms	364228 KB	Output is correct
30	Execution timed out	2029 ms	384136 KB	Time limit exceeded
31	Correct	1162 ms	149264 KB	Output is correct
32	Correct	1658 ms	333060 KB	Output is correct