oj.uz

답안 #427780

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
427780 2021-06-14T22:24:13 Z OkMaybe 바이러스 (JOI19_virus) C++14
100 / 100
 1212 ms 15756 KB 
#include <cstdio>
#include <algorithm>
#include <queue>

using namespace std;

const int INF = 1000000007;

int dc[4] = { 'N', 'W', 'S', 'E' };
int nexty[4] = { -1, 0, 1, 0 };
int nextx[4] = { 0, -1, 0, 1 };

bool inside(int R, int C, int y, int x) {
	return 0 <= y && y < R && 0 <= x && x < C;
}

bool inmax(int& a, int b) {
	if (b > a) {
		a = b;
		return true;
	}
	return false;
}

int ctod(char c) {
	for (int i = 0; i < 4; i++) {
		if (c == dc[i]) return i;
	}
	return -1;
}

int main() {
	int M, R, C;
	scanf("%d%d%d", &M, &R, &C);
	char D[M * 2];
	scanf("%s", D);
	for (int i = 0; i < M; i++) D[M + i] = D[i];
	int U[R][C];
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			scanf("%d", U[i] + j);
		}
	}

	int cnt[1 << 4];
	int thr[1 << 4];
	fill(cnt, cnt + (1 << 4), 0);
	fill(thr, thr + (1 << 4), 0);
	for (int i = 0; i < M * 2; i++) {
		int d = ctod(D[i]);
		for (int j = 0; j < (1 << 4); j++) {
			if ((j >> d) & 1) {
				cnt[j]++;
			}
			else {
				inmax(thr[j], cnt[j]);
				cnt[j] = 0;
			}
		}
	}
	for (int j = 0; j < (1 << 4); j++) {
		if (cnt[j] == M * 2) {
			thr[j] = INF;
		}
	}

	pair<int, int> cor[R * C];
	for (int i = 0; i < R; i++) {
		for (int j = 0; j < C; j++) {
			cor[C * i + j] = make_pair(i, j);
		}
	}
	random_shuffle(cor, cor + R * C);

	int min = INF;
	int cnt2 = 0;
	int cnt3 = 0;
	bool fin[R][C], stt[R][C];
	fill(fin[0], fin[R], false);
	fill(stt[0], stt[R], false);
	for (int i = 0; i < R * C; i++) {
		stt[cor[i].first][cor[i].second] = true;
		if (U[cor[i].first][cor[i].second] == 0) continue;
		queue<pair<int, int> > Q;
		queue<pair<int, int> > Q1;
		int cnt1 = 1;
		fin[cor[i].first][cor[i].second] = true;
		Q1.push(cor[i]);
		for (int k = 0; k < 4; k++) {
			int ny = cor[i].first + nexty[k];
			int nx = cor[i].second + nextx[k];
			if (inside(R, C, ny, nx)) Q.push(make_pair(ny, nx));
		}
		for (; !Q.empty();) {
			cnt3++;
			pair<int, int> rem = Q.front();
			Q.pop();
			if (U[rem.first][rem.second] == 0 || fin[rem.first][rem.second]) continue;
			int ds = 0;
			for (int k = 0; k < 4; k++) {
				if (inside(R, C, rem.first + nexty[k], rem.second + nextx[k]) && fin[rem.first + nexty[k]][rem.second + nextx[k]]) {
					ds += (1 << k);
				}
			}
			if (U[rem.first][rem.second] <= thr[ds]) {
				if (stt[rem.first][rem.second]) {
					cnt1 = -1;
					break;
				}
				cnt1++;
				fin[rem.first][rem.second] = true;
				Q1.push(make_pair(rem.first, rem.second));
				for (int k = 0; k < 4; k++) {
					int ny = rem.first + nexty[k];
					int nx = rem.second + nextx[k];
					if (inside(R, C, ny, nx)) Q.push(make_pair(ny, nx));
				}
			}
		}
		for (; !Q1.empty();) {
			fin[Q1.front().first][Q1.front().second] = false;
			Q1.pop();
		}
		if (cnt1 == -1) continue;
		if (cnt1 < min) {
			min = cnt1;
			cnt2 = 0;
		}
		if (cnt1 == min) cnt2 += cnt1;
	}

	printf("%d\n%d\n", min, cnt2);
	//fprintf(stderr, "%d\n", cnt3);
	return 0;
}

Compilation message

virus.cpp: In function 'int main()':
virus.cpp:34:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   34 |  scanf("%d%d%d", &M, &R, &C);
      |  ~~~~~^~~~~~~~~~~~~~~~~~~~~~
virus.cpp:36:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  scanf("%s", D);
      |  ~~~~~^~~~~~~~~
virus.cpp:41:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   41 |    scanf("%d", U[i] + j);
      |    ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 322 ms 9016 KB Output is correct
3 Correct 676 ms 9036 KB Output is correct
4 Correct 694 ms 9028 KB Output is correct
5 Correct 276 ms 9000 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 724 ms 9224 KB Output is correct
8 Correct 109 ms 3884 KB Output is correct

Subtask #2
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 9 ms 472 KB Output is correct
3 Correct 11 ms 460 KB Output is correct
4 Correct 6 ms 460 KB Output is correct
5 Correct 8 ms 460 KB Output is correct
6 Correct 13 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 9 ms 460 KB Output is correct
9 Correct 2 ms 204 KB Output is correct
10 Correct 7 ms 468 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 3 ms 332 KB Output is correct
13 Correct 11 ms 460 KB Output is correct
14 Correct 13 ms 480 KB Output is correct
15 Correct 12 ms 480 KB Output is correct
16 Correct 10 ms 480 KB Output is correct
17 Correct 6 ms 400 KB Output is correct
18 Correct 2 ms 204 KB Output is correct
19 Correct 9 ms 460 KB Output is correct

Subtask #3
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 332 KB Output is correct
2 Correct 322 ms 9016 KB Output is correct
3 Correct 676 ms 9036 KB Output is correct
4 Correct 694 ms 9028 KB Output is correct
5 Correct 276 ms 9000 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 724 ms 9224 KB Output is correct
8 Correct 109 ms 3884 KB Output is correct
9 Correct 1 ms 204 KB Output is correct
10 Correct 9 ms 472 KB Output is correct
11 Correct 11 ms 460 KB Output is correct
12 Correct 6 ms 460 KB Output is correct
13 Correct 8 ms 460 KB Output is correct
14 Correct 13 ms 460 KB Output is correct
15 Correct 0 ms 204 KB Output is correct
16 Correct 9 ms 460 KB Output is correct
17 Correct 2 ms 204 KB Output is correct
18 Correct 7 ms 468 KB Output is correct
19 Correct 2 ms 204 KB Output is correct
20 Correct 3 ms 332 KB Output is correct
21 Correct 11 ms 460 KB Output is correct
22 Correct 13 ms 480 KB Output is correct
23 Correct 12 ms 480 KB Output is correct
24 Correct 10 ms 480 KB Output is correct
25 Correct 6 ms 400 KB Output is correct
26 Correct 2 ms 204 KB Output is correct
27 Correct 9 ms 460 KB Output is correct
28 Correct 984 ms 15756 KB Output is correct
29 Correct 1031 ms 15724 KB Output is correct
30 Correct 906 ms 13896 KB Output is correct
31 Correct 853 ms 12484 KB Output is correct
32 Correct 891 ms 11124 KB Output is correct
33 Correct 390 ms 10448 KB Output is correct
34 Correct 1212 ms 15560 KB Output is correct
35 Correct 793 ms 11884 KB Output is correct
36 Correct 820 ms 10684 KB Output is correct
37 Correct 1126 ms 12428 KB Output is correct
38 Correct 962 ms 15412 KB Output is correct
39 Correct 390 ms 11556 KB Output is correct
40 Correct 392 ms 11536 KB Output is correct
41 Correct 392 ms 10532 KB Output is correct
42 Correct 837 ms 13532 KB Output is correct
43 Correct 1049 ms 13576 KB Output is correct
44 Correct 123 ms 5324 KB Output is correct