oj.uz

답안 #938043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938043 2024-03-04T18:32:47 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 1518 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; 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 178 ms 406864 KB Output is correct
2 Correct 159 ms 396908 KB Output is correct
3 Correct 139 ms 397096 KB Output is correct
4 Correct 159 ms 403732 KB Output is correct
5 Correct 143 ms 399700 KB Output is correct
6 Correct 149 ms 396908 KB Output is correct
7 Correct 140 ms 397136 KB Output is correct
8 Correct 138 ms 397192 KB Output is correct
9 Correct 139 ms 397564 KB Output is correct
10 Correct 143 ms 399384 KB Output is correct
11 Correct 154 ms 399184 KB Output is correct
12 Correct 149 ms 401240 KB Output is correct
13 Correct 143 ms 399568 KB Output is correct
14 Correct 141 ms 399700 KB Output is correct
15 Correct 162 ms 405476 KB Output is correct
16 Correct 170 ms 407044 KB Output is correct
17 Correct 156 ms 403540 KB Output is correct
18 Correct 147 ms 403548 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 150 ms 427716 KB Output is correct
2 Correct 242 ms 423344 KB Output is correct
3 Correct 731 ms 526128 KB Output is correct
4 Correct 279 ms 435416 KB Output is correct
5 Correct 796 ms 582360 KB Output is correct
6 Correct 1150 ms 640340 KB Output is correct
7 Correct 156 ms 429280 KB Output is correct
8 Correct 150 ms 427484 KB Output is correct
9 Correct 139 ms 397796 KB Output is correct
10 Correct 141 ms 397132 KB Output is correct
11 Correct 158 ms 428432 KB Output is correct
12 Correct 138 ms 398420 KB Output is correct
13 Correct 243 ms 423248 KB Output is correct
14 Correct 200 ms 413676 KB Output is correct
15 Correct 189 ms 413140 KB Output is correct
16 Correct 190 ms 408916 KB Output is correct
17 Correct 411 ms 454748 KB Output is correct
18 Correct 327 ms 445820 KB Output is correct
19 Correct 277 ms 435540 KB Output is correct
20 Correct 278 ms 435540 KB Output is correct
21 Correct 494 ms 482820 KB Output is correct
22 Correct 807 ms 582636 KB Output is correct
23 Correct 659 ms 498260 KB Output is correct
24 Correct 483 ms 484480 KB Output is correct
25 Correct 1069 ms 547428 KB Output is correct
26 Runtime error 546 ms 1048576 KB Execution killed with signal 9
27 Correct 1004 ms 976284 KB Output is correct
28 Correct 1161 ms 640516 KB Output is correct
29 Correct 1081 ms 646832 KB Output is correct
30 Correct 1061 ms 749204 KB Output is correct
31 Correct 1518 ms 695224 KB Output is correct
32 Correct 963 ms 882788 KB Output is correct