oj.uz

답안 #843115

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843115 2023-09-03T17:20:18 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++14
0 / 100
 2000 ms 963724 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-1;
}

Subtask #1
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 26 ms 31064 KB Output isn't correct
2 Incorrect 1 ms 6492 KB Output isn't correct
3 Incorrect 1 ms 6744 KB Output isn't correct
4 Incorrect 27 ms 31580 KB Output isn't correct
5 Incorrect 13 ms 22104 KB Output isn't correct
6 Incorrect 1 ms 6900 KB Output isn't correct
7 Incorrect 2 ms 6744 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 19800 KB Output isn't correct
11 Incorrect 9 ms 15904 KB Output isn't correct
12 Incorrect 12 ms 22108 KB Output isn't correct
13 Incorrect 13 ms 22104 KB Output isn't correct
14 Incorrect 13 ms 22108 KB Output isn't correct
15 Incorrect 27 ms 33112 KB Output isn't correct
16 Incorrect 26 ms 31064 KB Output isn't correct
17 Incorrect 28 ms 31128 KB Output isn't correct
18 Incorrect 27 ms 31576 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 214256 KB Output isn't correct
2 Incorrect 180 ms 73220 KB Output isn't correct
3 Incorrect 1967 ms 220140 KB Output isn't correct
4 Incorrect 494 ms 108624 KB Output isn't correct
5 Incorrect 455 ms 170612 KB Output isn't correct
6 Execution timed out 2036 ms 239440 KB Time limit exceeded
7 Incorrect 30 ms 218704 KB Output isn't correct
8 Incorrect 30 ms 214360 KB Output isn't correct
9 Incorrect 7 ms 7000 KB Output isn't correct
10 Incorrect 4 ms 6744 KB Output isn't correct
11 Incorrect 31 ms 218392 KB Output isn't correct
12 Incorrect 3 ms 13148 KB Output isn't correct
13 Incorrect 179 ms 73224 KB Output isn't correct
14 Incorrect 104 ms 57432 KB Output isn't correct
15 Incorrect 106 ms 59736 KB Output isn't correct
16 Incorrect 67 ms 28848 KB Output isn't correct
17 Incorrect 448 ms 115300 KB Output isn't correct
18 Incorrect 422 ms 115020 KB Output isn't correct
19 Incorrect 492 ms 108604 KB Output isn't correct
20 Incorrect 421 ms 99884 KB Output isn't correct
21 Incorrect 1137 ms 175064 KB Output isn't correct
22 Incorrect 523 ms 170320 KB Output isn't correct
23 Incorrect 848 ms 144020 KB Output isn't correct
24 Incorrect 858 ms 174928 KB Output isn't correct
25 Incorrect 1618 ms 220112 KB Output isn't correct
26 Execution timed out 2068 ms 963724 KB Time limit exceeded
27 Execution timed out 2041 ms 420672 KB Time limit exceeded
28 Execution timed out 2009 ms 239460 KB Time limit exceeded
29 Execution timed out 2056 ms 245584 KB Time limit exceeded
30 Execution timed out 2037 ms 237780 KB Time limit exceeded
31 Incorrect 932 ms 181932 KB Output isn't correct
32 Execution timed out 2039 ms 219892 KB Time limit exceeded