oj.uz

답안 #843118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
843118 2023-09-03T17:23:30 Z Mizo_Compiler Tracks in the Snow (BOI13_tracks) C++17
27.3958 / 100
 2000 ms 964172 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;
}

Subtask #1
3.33333333333 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 31068 KB Output isn't correct
2 Correct 1 ms 6492 KB Output is correct
3 Incorrect 1 ms 6748 KB Output isn't correct
4 Incorrect 27 ms 31788 KB Output isn't correct
5 Incorrect 5 ms 22108 KB Output isn't correct
6 Correct 1 ms 6492 KB Output is correct
7 Incorrect 1 ms 6748 KB Output isn't correct
8 Incorrect 2 ms 8796 KB Output isn't correct
9 Incorrect 1 ms 9052 KB Output isn't correct
10 Incorrect 5 ms 19804 KB Output isn't correct
11 Incorrect 8 ms 15848 KB Output isn't correct
12 Incorrect 10 ms 22420 KB Output isn't correct
13 Incorrect 5 ms 22108 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 31068 KB Output isn't correct
18 Incorrect 27 ms 31580 KB Output isn't correct

Subtask #2
24.0625 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 28 ms 214108 KB Output is correct
2 Incorrect 65 ms 73052 KB Output isn't correct
3 Incorrect 387 ms 220136 KB Output isn't correct
4 Incorrect 90 ms 108372 KB Output isn't correct
5 Correct 146 ms 170460 KB Output is correct
6 Execution timed out 2021 ms 239440 KB Time limit exceeded
7 Correct 27 ms 218700 KB Output is correct
8 Correct 27 ms 214104 KB Output is correct
9 Incorrect 4 ms 6748 KB Output isn't correct
10 Correct 2 ms 6748 KB Output is correct
11 Incorrect 26 ms 218368 KB Output isn't correct
12 Correct 2 ms 13148 KB Output is correct
13 Incorrect 68 ms 73216 KB Output isn't correct
14 Incorrect 39 ms 57436 KB Output isn't correct
15 Correct 36 ms 59736 KB Output is correct
16 Incorrect 34 ms 28848 KB Output isn't correct
17 Incorrect 155 ms 115296 KB Output isn't correct
18 Correct 112 ms 115032 KB Output is correct
19 Incorrect 91 ms 108624 KB Output isn't correct
20 Incorrect 96 ms 99884 KB Output isn't correct
21 Incorrect 235 ms 175064 KB Output isn't correct
22 Correct 140 ms 170556 KB Output is correct
23 Incorrect 290 ms 144004 KB Output isn't correct
24 Correct 234 ms 174932 KB Output is correct
25 Correct 430 ms 220112 KB Output is correct
26 Execution timed out 2062 ms 964172 KB Time limit exceeded
27 Execution timed out 2054 ms 420636 KB Time limit exceeded
28 Execution timed out 2015 ms 239444 KB Time limit exceeded
29 Execution timed out 2057 ms 245604 KB Time limit exceeded
30 Execution timed out 2016 ms 237620 KB Time limit exceeded
31 Incorrect 927 ms 181796 KB Output isn't correct
32 Execution timed out 2025 ms 219984 KB Time limit exceeded