Submission #227471

#	Time	Username	Problem	Language	Result	Execution time	Memory
227471		wilwxk	Virus Experiment (JOI19_virus)	C++14	100 / 100	687 ms	24272 KiB

virus

#include <bits/stdc++.h>
using namespace std;
 
const int MAXN = 805;
char comb[212345];
int sick[20];
int resis[MAXN][MAXN];
int marc[MAXN][MAXN];
bool checked[MAXN][MAXN];
vector<pair<int, int> > perm;
int x, n, m;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};
int dc[] = {'E', 'S', 'W', 'N'};
int ans, ans2;
 
void calc_comb() {
	for(int i = x+1; i <= x+x; i++) comb[i] = comb[i-x];
 
	for(int mask = 0; mask < (1<<4); mask++) {
		int mx = 0, cnt = 0;
		for(int i = 1; i <= x+x; i++) {
			bool ok = 0;
			for(int k = 0; k < 4; k++) {
				if(((1<<k)&mask) && dc[k] == comb[i]) {
					ok = 1;
					cnt++;
				}
			}
			mx = max(mx, cnt);
			if(!ok) cnt = 0;
		}
		if(mx == x+x) mx = 1e6;
		sick[mask] = mx;
		// printf("mask[%d] -> %d\n", mask, mx);
	}
}
 
bool isvalid(int i, int j) {
	if(i < 1 || i > n) return 0;
	if(j < 1 || j > m) return 0;
	return 1;
}
 
int bfs(int ox, int oy) {
	int cnt = 0;
 
	vector<pair<int, int> > qu;
	qu.push_back({ox, oy});
	int p = 0;
 
	while(p < qu.size()) {
		int ux, uy;
		tie(ux, uy) = qu[p++];
		if(marc[ux][uy] == 1) continue;
		marc[ux][uy] = 1;
		cnt++;
		if(cnt > ans) {
			for(auto cur : qu) marc[cur.first][cur.second] = 0;
			return -1;
		} 
		for(int k = 0; k < 4; k++) {
			int vx = ux + dx[k];
			int vy = uy + dy[k];
			if(!isvalid(vx, vy)) continue;
			if(marc[vx][vy] || resis[vx][vy] == 0) continue;
 
			int mask = 0;
			for(int k2 = 0; k2 < 4; k2++) {
				int vx2 = vx + dx[k2];
				int vy2 = vy + dy[k2];
				if(!isvalid(vx2, vy2)) continue;
				if(marc[vx2][vy2]) mask |= (1<<k2);
			}
 
			if(sick[mask] >= resis[vx][vy]) {
				// printf("  add %d %d - %d\n", vx, vy, mask);
				if(checked[vx][vy]) {
					for(auto cur : qu) marc[cur.first][cur.second] = 0;
					return -1;
				}
				marc[vx][vy] = 2;
				qu.push_back({vx, vy});
			}
		}
	}
 
	for(auto cur : qu) marc[cur.first][cur.second] = 0;
 
	return cnt;
}
 
int main() {
	scanf("%d %d %d", &x, &n, &m);
	ans = n*m;
	scanf(" %s", &comb[1]);
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= m; j++) {
			scanf("%d", &resis[i][j]);
			perm.push_back({i, j});
		}
	}
 
	calc_comb();
 
	srand(time(0));
	random_shuffle(perm.begin(), perm.end());
	for(auto cur : perm) {
		int cx, cy;
		tie(cx, cy) = cur;
		checked[cx][cy] = 1;
		if(resis[cx][cy] == 0) continue;
		int val = bfs(cx, cy);
 
		// printf("%d %d >>> %d\n", cx, cy, val);
		if(val == -1) continue;
		if(val < ans) {
			ans = val;
			ans2 = 0;
		}
		if(val == ans) ans2 += ans;
	}
 
	printf("%d\n%d\n", ans, ans2);
}

Compilation message (stderr)

virus.cpp: In function 'int bfs(int, int)':
virus.cpp:52:10: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  while(p < qu.size()) {
        ~~^~~~~~~~~~~
virus.cpp: In function 'int main()':
virus.cpp:94:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d", &x, &n, &m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
virus.cpp:96:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", &comb[1]);
  ~~~~~^~~~~~~~~~~~~~~~~
virus.cpp:99:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &resis[i][j]);
    ~~~~~^~~~~~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 6 / 6
• Subtask 3: 80 / 80