oj.uz

답안 #843114

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843114 2023-09-03T17:18:19 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++14
2.1875 / 100
 2000 ms 975540 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef double ld;
#define pb push_back
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define F first
#define S second
const int N = 4000;
int n, m, ans = 1, sz[N][N];
pair<int, int> p[N][N];
char c[N][N];
bool fc[N][N];
int dx[] = {1, -1, 0, 0};
int dy[] = {0, 0, 1, -1};

void dfs(int i, int j) {
	fc[i][j] = true;
	for (int ii = 0; ii < 4; ii++) {
		int nx = i + dx[ii], ny = j + dy[ii];
		if (nx >= 0 && ny >= 0 && nx < n && ny < m && c[nx][ny] == c[0][0] && !fc[nx][ny]) {
			dfs(nx, ny);
		}
	}
}

pair<int, int> findp(int i, int j) {
	return p[i][j] = (p[i][j].F == i && p[i][j].S == j ? p[i][j] : findp(p[i][j].F, p[i][j].S));
}

void merge(int i, int j, int x, int y) {
	pair<int, int> f = findp(i, j), s = findp(x, y);
	if (f == s)return;
	if (sz[s.F][s.S] > sz[f.F][f.S])swap(f, s);
	p[s.F][s.S] = f;
}

int main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			cin >> c[i][j];
			p[i][j] = {i, j};
			sz[i][j] = 1;
		}
	}
	dfs(0, 0);
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			for (int k = 0; k < 4; k++) {
				int nx = i + dx[k], ny = j + dy[k];
				if (nx < 0 || ny < 0 || nx >= n || ny >= m)continue;
				if (c[nx][ny] == c[i][j] || fc[nx][ny]) {
					merge(i, j, nx, ny);
				}
			}
		}
	}
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (p[i][j].F == i && p[i][j].S == j) {
				ans++;
			}
		}
	}
	cout << ans;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31320 KB Output isn't correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Incorrect 2 ms 6748 KB Output isn't correct
4 Incorrect 28 ms 31832 KB Output isn't correct
5 Incorrect 13 ms 22104 KB Output isn't correct
6 Incorrect 1 ms 6488 KB Output isn't correct
7 Incorrect 1 ms 6748 KB Output isn't correct
8 Incorrect 2 ms 8792 KB Output isn't correct
9 Incorrect 3 ms 9048 KB Output isn't correct
10 Incorrect 10 ms 19804 KB Output isn't correct
11 Incorrect 8 ms 15704 KB Output isn't correct
12 Incorrect 10 ms 22104 KB Output isn't correct
13 Incorrect 13 ms 22112 KB Output isn't correct
14 Incorrect 13 ms 21980 KB Output isn't correct
15 Incorrect 28 ms 33368 KB Output isn't correct
16 Incorrect 25 ms 31320 KB Output isn't correct
17 Incorrect 27 ms 31336 KB Output isn't correct
18 Incorrect 28 ms 32080 KB Output isn't correct

Subtask #2
2.1875 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 32 ms 214096 KB Output isn't correct
2 Incorrect 177 ms 74832 KB Output isn't correct
3 Incorrect 1964 ms 235496 KB Output isn't correct
4 Incorrect 493 ms 112264 KB Output isn't correct
5 Incorrect 458 ms 179264 KB Output isn't correct
6 Execution timed out 2029 ms 254800 KB Time limit exceeded
7 Incorrect 30 ms 218704 KB Output isn't correct
8 Incorrect 31 ms 214180 KB Output isn't correct
9 Incorrect 8 ms 7000 KB Output isn't correct
10 Correct 5 ms 6744 KB Output is correct
11 Incorrect 31 ms 218460 KB Output isn't correct
12 Incorrect 3 ms 13144 KB Output isn't correct
13 Incorrect 181 ms 74748 KB Output isn't correct
14 Incorrect 104 ms 58200 KB Output isn't correct
15 Incorrect 107 ms 60848 KB Output isn't correct
16 Incorrect 68 ms 29272 KB Output isn't correct
17 Incorrect 458 ms 119380 KB Output isn't correct
18 Incorrect 418 ms 119120 KB Output isn't correct
19 Incorrect 498 ms 112076 KB Output isn't correct
20 Incorrect 422 ms 103248 KB Output isn't correct
21 Incorrect 1118 ms 184144 KB Output isn't correct
22 Incorrect 463 ms 179268 KB Output isn't correct
23 Incorrect 860 ms 151552 KB Output isn't correct
24 Incorrect 864 ms 183828 KB Output isn't correct
25 Incorrect 1641 ms 235580 KB Output isn't correct
26 Execution timed out 2069 ms 975540 KB Time limit exceeded
27 Execution timed out 2114 ms 436108 KB Time limit exceeded
28 Execution timed out 2005 ms 254804 KB Time limit exceeded
29 Execution timed out 2013 ms 260888 KB Time limit exceeded
30 Execution timed out 2017 ms 252464 KB Time limit exceeded
31 Incorrect 921 ms 191776 KB Output isn't correct
32 Execution timed out 2101 ms 235364 KB Time limit exceeded