Submission #427780

#	Time	Username	Problem	Language	Result	Execution time	Memory
427780		OkMaybe	Virus Experiment (JOI19_virus)	C++14	100 / 100	1212 ms	15756 KiB

virus

#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 (stderr)

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 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80