oj.uz

답안 #843120

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843120 2023-09-03T17:24:17 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 963672 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++) {
          if (c[i][j] == '.')continue;
			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 (c[i][j] == '.')continue;
			if (p[i][j].F == i && p[i][j].S == j) {
				ans++;
			}
		}
	}
	cout << ans-1;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 31064 KB Output isn't correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Incorrect 28 ms 31580 KB Output isn't correct
5 Incorrect 6 ms 22104 KB Output isn't correct
6 Incorrect 1 ms 6492 KB Output isn't correct
7 Incorrect 1 ms 6748 KB Output isn't correct
8 Incorrect 2 ms 8936 KB Output isn't correct
9 Incorrect 1 ms 9048 KB Output isn't correct
10 Incorrect 6 ms 19800 KB Output isn't correct
11 Incorrect 9 ms 15708 KB Output isn't correct
12 Incorrect 11 ms 22108 KB Output isn't correct
13 Incorrect 5 ms 22012 KB Output isn't correct
14 Incorrect 5 ms 22108 KB Output isn't correct
15 Incorrect 20 ms 33280 KB Output isn't correct
16 Incorrect 26 ms 31068 KB Output isn't correct
17 Incorrect 14 ms 30984 KB Output isn't correct
18 Incorrect 29 ms 31792 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 214108 KB Output isn't correct
2 Incorrect 65 ms 73052 KB Output isn't correct
3 Incorrect 400 ms 219904 KB Output isn't correct
4 Incorrect 94 ms 108604 KB Output isn't correct
5 Incorrect 145 ms 170372 KB Output isn't correct
6 Execution timed out 2067 ms 239488 KB Time limit exceeded
7 Incorrect 28 ms 218720 KB Output isn't correct
8 Incorrect 28 ms 214108 KB Output isn't correct
9 Incorrect 4 ms 6748 KB Output isn't correct
10 Incorrect 2 ms 6748 KB Output isn't correct
11 Incorrect 28 ms 218436 KB Output isn't correct
12 Incorrect 2 ms 13148 KB Output isn't correct
13 Incorrect 67 ms 73004 KB Output isn't correct
14 Incorrect 43 ms 57504 KB Output isn't correct
15 Incorrect 33 ms 59692 KB Output isn't correct
16 Incorrect 36 ms 28860 KB Output isn't correct
17 Incorrect 157 ms 115300 KB Output isn't correct
18 Incorrect 115 ms 114996 KB Output isn't correct
19 Incorrect 90 ms 108596 KB Output isn't correct
20 Incorrect 102 ms 99888 KB Output isn't correct
21 Incorrect 249 ms 174908 KB Output isn't correct
22 Incorrect 145 ms 170340 KB Output isn't correct
23 Incorrect 292 ms 143908 KB Output isn't correct
24 Incorrect 238 ms 175120 KB Output isn't correct
25 Incorrect 432 ms 219904 KB Output isn't correct
26 Execution timed out 2088 ms 963672 KB Time limit exceeded
27 Execution timed out 2084 ms 420660 KB Time limit exceeded
28 Execution timed out 2040 ms 239412 KB Time limit exceeded
29 Execution timed out 2082 ms 245544 KB Time limit exceeded
30 Execution timed out 2064 ms 237544 KB Time limit exceeded
31 Incorrect 934 ms 181812 KB Output isn't correct
32 Execution timed out 2044 ms 219988 KB Time limit exceeded