oj.uz

답안 #938044

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938044 2024-03-04T18:33:42 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 1553 ms 1048576 KB 
#include <bits/stdc++.h>
using namespace std;
int dx[4] = {0, -1, 0, 1};
int dy[4] = {1, 0, -1, 0};
const int MAXN = 4025;
int comp[MAXN][MAXN];
char arr[MAXN][MAXN]; 
int n, m;
bool check (int i, int j) {
	return (i >= 0 && i < n && j >= 0 && j < m && arr[i][j] != '.');
}
void dfs (int i, int j) {
	for (int l = 0; l < 4; l++) {
		if (check(i + dx[l], j + dy[l]) && comp[i + dx[l]][j + dy[l]] == 0 && arr[i + dx[l]][j + dy[l]] == arr[i][j]) {
			comp[i + dx[l]][j + dy[l]] = comp[i][j];
			dfs(i + dx[l], j + dy[l]);
		}
	}
}
vector <int> adj[MAXN * MAXN];
bool vis[MAXN * MAXN];
queue <int> cur;
signed main () {
	ios::sync_with_stdio(0); cin.tie(0);
	memset(vis, false, sizeof(vis));
	cin >> n >> m; assert(n < MAXN); assert(m < MAXN); for (int i = 0; i < n; i++) for (int j = 0; j < m; j++) cin >> arr[i][j];
	int c = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (comp[i][j] == 0 && arr[i][j] != '.') {
				c++;
				comp[i][j] = c;
				dfs(i, j);
			}
		}
	}
	assert(c < MAXN * MAXN);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (arr[i][j] == '.') continue;
			for (int l = 0; l < 4; l++) {
				if (check(i + dx[l], j + dy[l])) {
					if (comp[i + dx[l]][j + dy[l]] != comp[i][j]) {
						adj[comp[i][j]].push_back(comp[i + dx[l]][j + dy[l]]);
						adj[comp[i + dx[l]][j + dy[l]]].push_back(comp[i][j]);
					}
				}
			}
		}
	}
 	cur.push(comp[0][0]); vis[comp[0][0]] = 1;
	int cnt = 1;
	int ans = 0;
	while (!cur.empty()) {
		auto u = cur.size(); while (u--) {
			int k = cur.front(); cur.pop(); 
			ans = cnt;
			while (!adj[k].empty()) {
				int j = adj[k].back();
				adj[k].pop_back();
				if (!vis[j]) {
					vis[j] = 1; cur.push(j);
				}
			}
		}
		cnt++;
	}
	cout << ans << '\n';
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 200 ms 406864 KB Output is correct
2 Correct 140 ms 397140 KB Output is correct
3 Correct 133 ms 397136 KB Output is correct
4 Correct 143 ms 403640 KB Output is correct
5 Correct 140 ms 399696 KB Output is correct
6 Correct 138 ms 397116 KB Output is correct
7 Correct 137 ms 397136 KB Output is correct
8 Correct 134 ms 397140 KB Output is correct
9 Correct 139 ms 397532 KB Output is correct
10 Correct 139 ms 399240 KB Output is correct
11 Correct 137 ms 399184 KB Output is correct
12 Correct 145 ms 401236 KB Output is correct
13 Correct 144 ms 400040 KB Output is correct
14 Correct 139 ms 399696 KB Output is correct
15 Correct 163 ms 405460 KB Output is correct
16 Correct 168 ms 406868 KB Output is correct
17 Correct 158 ms 403536 KB Output is correct
18 Correct 149 ms 403664 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 148 ms 427668 KB Output is correct
2 Correct 236 ms 423304 KB Output is correct
3 Correct 731 ms 526396 KB Output is correct
4 Correct 268 ms 435540 KB Output is correct
5 Correct 761 ms 582276 KB Output is correct
6 Correct 1176 ms 640612 KB Output is correct
7 Correct 150 ms 429308 KB Output is correct
8 Correct 146 ms 427616 KB Output is correct
9 Correct 136 ms 397656 KB Output is correct
10 Correct 135 ms 397140 KB Output is correct
11 Correct 144 ms 428284 KB Output is correct
12 Correct 135 ms 398332 KB Output is correct
13 Correct 235 ms 423076 KB Output is correct
14 Correct 195 ms 413700 KB Output is correct
15 Correct 181 ms 412968 KB Output is correct
16 Correct 188 ms 409040 KB Output is correct
17 Correct 412 ms 454728 KB Output is correct
18 Correct 326 ms 445776 KB Output is correct
19 Correct 269 ms 435436 KB Output is correct
20 Correct 277 ms 435532 KB Output is correct
21 Correct 489 ms 482896 KB Output is correct
22 Correct 755 ms 582404 KB Output is correct
23 Correct 683 ms 498616 KB Output is correct
24 Correct 496 ms 484692 KB Output is correct
25 Correct 1012 ms 547188 KB Output is correct
26 Runtime error 588 ms 1048576 KB Execution killed with signal 9
27 Correct 991 ms 976312 KB Output is correct
28 Correct 1169 ms 640560 KB Output is correct
29 Correct 1128 ms 646948 KB Output is correct
30 Correct 1063 ms 749592 KB Output is correct
31 Correct 1553 ms 695180 KB Output is correct
32 Correct 965 ms 882520 KB Output is correct