Submission #767661

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
767661	2023-06-27T02:52:32 Z	lukehsiao	Tracks in the Snow (BOI13_tracks)	C++14	5.52083 / 100	1398 ms	1048576 KB

tracks

#include <bits/stdc++.h>
using namespace std;

const int mxN = 4000;

int H, W, id[mxN][mxN];
char grid[mxN][mxN];
int dx[4]{1, -1, 0, 0}, dy[4]{0, 0, 1, -1};

vector<set<int>> adj;
vector<int> dist;

void ff(int r, int c, int x) {
	id[r][c] = x;
	
	for (int i=0; i<4; ++i) {
		int nr = r + dx[i], nc = c + dy[i];
		if (nr >= 0 && nr < H && nc >= 0 && nc < W &&
				grid[nr][nc] == grid[r][c] && !id[nr][nc]) {
			ff(nr, nc, x);
		}
	}
}

void ff2(int r, int c, int x) {
	id[r][c] = 0;

	for (int i=0; i<4; ++i) {
		int nr = r + dx[i], nc = c + dy[i];
		if (nr >= 0 && nr < H && nc >= 0 && nc < W && id[nr][nc]) {
			if (id[nr][nc] != x)
				adj[x-1].insert(id[nr][nc]-1);
			else
				ff2(nr, nc, x);
		}
	}
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);

	cin >> H >> W;
	for (int i=0; i<H; ++i)
		for (int j=0; j<W; ++j)
			cin >> grid[i][j];
	
	int cur = 0;
	for (int i=0; i<H; ++i) {
		for (int j=0; j<W; ++j) {
			if (!id[i][j] && grid[i][j] != '.')
				ff(i, j, ++cur);
		}
	}

	adj.resize(cur);
	dist.resize(cur, 2e9);

	for (int i=0; i<H; ++i) {
		for (int j=0; j<W; ++j) {
			if (id[i][j]) {
				ff2(i, j, id[i][j]);
			}
		}
	}

	queue<int> q;
	q.push(0);
	dist[0] = 0;

	while (!q.empty()) {
		int x = q.front();
		q.pop();
		for (int u : adj[x]) {
			if (dist[u] == 2e9) {
				dist[u] = dist[x] + 1;
				q.push(u);
			}
		}
	}

	int ans = 0;
	for (int i : dist)
		ans = max(ans, i);
	
	cout << ans + 1 << '\n';
}

Subtask #1

3.33333333333 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	32 ms	9736 KB	Output isn't correct
2	Incorrect	1 ms	452 KB	Output isn't correct
3	Incorrect	1 ms	724 KB	Output isn't correct
4	Incorrect	12 ms	6260 KB	Output isn't correct
5	Incorrect	5 ms	3804 KB	Output isn't correct
6	Incorrect	1 ms	468 KB	Output isn't correct
7	Incorrect	1 ms	724 KB	Output isn't correct
8	Correct	1 ms	844 KB	Output is correct
9	Incorrect	2 ms	1236 KB	Output isn't correct
10	Incorrect	5 ms	3412 KB	Output isn't correct
11	Correct	4 ms	2516 KB	Output is correct
12	Incorrect	12 ms	4684 KB	Output isn't correct
13	Incorrect	5 ms	3796 KB	Output isn't correct
14	Incorrect	5 ms	3796 KB	Output isn't correct
15	Incorrect	24 ms	9404 KB	Output isn't correct
16	Incorrect	30 ms	9676 KB	Output isn't correct
17	Incorrect	17 ms	9212 KB	Output isn't correct
18	Incorrect	12 ms	6228 KB	Output isn't correct

Subtask #2

2.1875 / 70.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	14 ms	31572 KB	Output isn't correct
2	Incorrect	84 ms	36200 KB	Output isn't correct
3	Incorrect	476 ms	221844 KB	Output isn't correct
4	Incorrect	141 ms	58956 KB	Output isn't correct
5	Incorrect	556 ms	493724 KB	Output isn't correct
6	Incorrect	1290 ms	196224 KB	Output isn't correct
7	Incorrect	18 ms	32852 KB	Output isn't correct
8	Incorrect	16 ms	31572 KB	Output isn't correct
9	Incorrect	4 ms	1752 KB	Output isn't correct
10	Incorrect	1 ms	980 KB	Output isn't correct
11	Incorrect	17 ms	32028 KB	Output isn't correct
12	Incorrect	3 ms	2616 KB	Output isn't correct
13	Incorrect	90 ms	36172 KB	Output isn't correct
14	Incorrect	48 ms	22768 KB	Output isn't correct
15	Incorrect	41 ms	27212 KB	Output isn't correct
16	Incorrect	43 ms	15680 KB	Output isn't correct
17	Incorrect	239 ms	83532 KB	Output isn't correct
18	Incorrect	151 ms	89868 KB	Output isn't correct
19	Incorrect	115 ms	58896 KB	Output isn't correct
20	Incorrect	117 ms	59496 KB	Output isn't correct
21	Incorrect	283 ms	141452 KB	Output isn't correct
22	Incorrect	512 ms	493676 KB	Output isn't correct
23	Incorrect	437 ms	149068 KB	Output isn't correct
24	Incorrect	341 ms	196900 KB	Output isn't correct
25	Incorrect	613 ms	317716 KB	Output isn't correct
26	Runtime error	1398 ms	1048576 KB	Execution killed with signal 9
27	Correct	1020 ms	397564 KB	Output is correct
28	Incorrect	1286 ms	196120 KB	Output isn't correct
29	Incorrect	1154 ms	165884 KB	Output isn't correct
30	Incorrect	1187 ms	226124 KB	Output isn't correct
31	Incorrect	1302 ms	251236 KB	Output isn't correct
32	Incorrect	1271 ms	435812 KB	Output isn't correct