oj.uz

Submission #934136

# Submission time Handle Problem Language Result Execution time Memory
934136 2024-02-26T21:03:12 Z De3b0o Virus Experiment (JOI19_virus) C++14
6 / 100
 2000 ms 12628 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);
		}
	}
 
	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
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 179 ms 10476 KB Output is correct
3 Execution timed out 2043 ms 12628 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 5 ms 604 KB Output is correct
3 Correct 6 ms 604 KB Output is correct
4 Correct 3 ms 712 KB Output is correct
5 Correct 6 ms 600 KB Output is correct
6 Correct 6 ms 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 5 ms 692 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 4 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 1 ms 348 KB Output is correct
13 Correct 9 ms 772 KB Output is correct
14 Correct 9 ms 604 KB Output is correct
15 Correct 9 ms 604 KB Output is correct
16 Correct 5 ms 684 KB Output is correct
17 Correct 3 ms 604 KB Output is correct
18 Correct 1 ms 348 KB Output is correct
19 Correct 6 ms 736 KB Output is correct

Subtask #3
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 179 ms 10476 KB Output is correct
3 Execution timed out 2043 ms 12628 KB Time limit exceeded
4 Halted 0 ms 0 KB -