oj.uz

답안 #843117

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843117 2023-09-03T17:22:44 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++17
0 / 100
 2000 ms 963668 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 6488 KB Output isn't correct
3 Incorrect 1 ms 7000 KB Output isn't correct
4 Incorrect 28 ms 31580 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 6744 KB Output isn't correct
8 Incorrect 2 ms 8796 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 15704 KB Output isn't correct
12 Incorrect 10 ms 22164 KB Output isn't correct
13 Incorrect 13 ms 22104 KB Output isn't correct
14 Incorrect 13 ms 22104 KB Output isn't correct
15 Incorrect 27 ms 33116 KB Output isn't correct
16 Incorrect 25 ms 31064 KB Output isn't correct
17 Incorrect 28 ms 31064 KB Output isn't correct
18 Incorrect 29 ms 31580 KB Output isn't correct

Subtask #2
0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 30 ms 214028 KB Output isn't correct
2 Incorrect 175 ms 73048 KB Output isn't correct
3 Incorrect 1948 ms 220144 KB Output isn't correct
4 Incorrect 489 ms 108368 KB Output isn't correct
5 Incorrect 457 ms 170520 KB Output isn't correct
6 Execution timed out 2024 ms 239440 KB Time limit exceeded
7 Incorrect 30 ms 218688 KB Output isn't correct
8 Incorrect 33 ms 214096 KB Output isn't correct
9 Incorrect 7 ms 6744 KB Output isn't correct
10 Incorrect 4 ms 6744 KB Output isn't correct
11 Incorrect 32 ms 218380 KB Output isn't correct
12 Incorrect 3 ms 13148 KB Output isn't correct
13 Incorrect 177 ms 73048 KB Output isn't correct
14 Incorrect 105 ms 57432 KB Output isn't correct
15 Incorrect 106 ms 59736 KB Output isn't correct
16 Incorrect 75 ms 28760 KB Output isn't correct
17 Incorrect 445 ms 115296 KB Output isn't correct
18 Incorrect 422 ms 115452 KB Output isn't correct
19 Incorrect 493 ms 108608 KB Output isn't correct
20 Incorrect 421 ms 99888 KB Output isn't correct
21 Incorrect 1115 ms 175184 KB Output isn't correct
22 Incorrect 452 ms 170736 KB Output isn't correct
23 Incorrect 838 ms 144232 KB Output isn't correct
24 Incorrect 858 ms 174884 KB Output isn't correct
25 Incorrect 1622 ms 220108 KB Output isn't correct
26 Execution timed out 2083 ms 963668 KB Time limit exceeded
27 Execution timed out 2050 ms 420944 KB Time limit exceeded
28 Execution timed out 2050 ms 239440 KB Time limit exceeded
29 Execution timed out 2036 ms 245584 KB Time limit exceeded
30 Execution timed out 2025 ms 237604 KB Time limit exceeded
31 Incorrect 936 ms 182100 KB Output isn't correct
32 Execution timed out 2033 ms 219864 KB Time limit exceeded