oj.uz

답안 #938042

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
938042 2024-03-04T18:30:32 Z TAhmed33 Tracks in the Snow (BOI13_tracks) C++
97.8125 / 100
 1527 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 = 4000;
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 187 ms 402004 KB Output is correct
2 Correct 138 ms 391996 KB Output is correct
3 Correct 139 ms 392272 KB Output is correct
4 Correct 149 ms 398540 KB Output is correct
5 Correct 143 ms 394580 KB Output is correct
6 Correct 149 ms 391764 KB Output is correct
7 Correct 141 ms 392440 KB Output is correct
8 Correct 143 ms 392440 KB Output is correct
9 Correct 140 ms 392688 KB Output is correct
10 Correct 146 ms 394328 KB Output is correct
11 Correct 141 ms 394324 KB Output is correct
12 Correct 151 ms 396188 KB Output is correct
13 Correct 143 ms 394632 KB Output is correct
14 Correct 142 ms 394756 KB Output is correct
15 Correct 164 ms 400404 KB Output is correct
16 Correct 188 ms 402008 KB Output is correct
17 Correct 160 ms 398512 KB Output is correct
18 Correct 153 ms 399056 KB Output is correct

Subtask #2
67.8125 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 152 ms 422780 KB Output is correct
2 Correct 245 ms 418384 KB Output is correct
3 Correct 723 ms 520736 KB Output is correct
4 Correct 279 ms 430660 KB Output is correct
5 Correct 786 ms 577360 KB Output is correct
6 Correct 1156 ms 635128 KB Output is correct
7 Correct 153 ms 424272 KB Output is correct
8 Correct 157 ms 422924 KB Output is correct
9 Correct 143 ms 392788 KB Output is correct
10 Correct 143 ms 392276 KB Output is correct
11 Correct 152 ms 423252 KB Output is correct
12 Correct 144 ms 393392 KB Output is correct
13 Correct 244 ms 418388 KB Output is correct
14 Correct 197 ms 408660 KB Output is correct
15 Correct 189 ms 408400 KB Output is correct
16 Correct 188 ms 404056 KB Output is correct
17 Correct 407 ms 449828 KB Output is correct
18 Correct 332 ms 441140 KB Output is correct
19 Correct 272 ms 430448 KB Output is correct
20 Correct 281 ms 430780 KB Output is correct
21 Correct 487 ms 477884 KB Output is correct
22 Correct 792 ms 577236 KB Output is correct
23 Correct 666 ms 493352 KB Output is correct
24 Correct 488 ms 479828 KB Output is correct
25 Correct 1048 ms 542028 KB Output is correct
26 Runtime error 585 ms 1048576 KB Execution killed with signal 9
27 Correct 1014 ms 971164 KB Output is correct
28 Correct 1149 ms 635020 KB Output is correct
29 Correct 1078 ms 641532 KB Output is correct
30 Correct 1048 ms 743832 KB Output is correct
31 Correct 1527 ms 690088 KB Output is correct
32 Correct 960 ms 877064 KB Output is correct