Submission #193701

#	Time	Username	Problem	Language	Result	Execution time	Memory
193701		gs14004	Virus Experiment (JOI19_virus)	C++17	0 / 100	2037 ms	15072 KiB

virus

#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
using namespace std;
using lint = long long;
using pi = pair<int, int>;
const int MAXN = 808;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};

int n, m, dead[MAXN][MAXN];
bool good[MAXN][MAXN][16];
bool vis[MAXN][MAXN];
int ind[MAXN][MAXN];

bool ok(int x, int y){
	return x >= 0 && x < n && y >= 0 && y < m && !vis[x][y];
}
int reach(int x, int y){
	if(dead[x][y]) return 1e9;
	vector<pi> que;
	vis[x][y] = 1;
	que.emplace_back(x, y);
	for(int i=0; i<sz(que); i++){
		auto pnt = que[i];
		for(int j=0; j<4; j++){
			int nx = pnt.first + dx[j];
			int ny = pnt.second + dy[j];
			if(ok(nx, ny)){
				ind[nx][ny] |= (1<<j);
				if(good[nx][ny][ind[nx][ny]]){
					vis[nx][ny] = 1;
					que.emplace_back(nx, ny);
				}
			}
		}
	}
	for(auto &[x, y] : que){
		ind[x][y] = 0;
		vis[x][y] = 0;
	}
	return sz(que);
}

void solve(){
	int dap = 1e9;
	int cnt = 0;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int val = reach(i, j);
			if(dap > val){
				dap = val;
				cnt = 0;
			}
			if(dap == val) cnt++;
		}
	}
	printf("%d %d\n", dap, cnt);
}

char buf[200005];

int main(){
	int mp[256];
	mp['N'] = 0;
	mp['W'] = 1;
	mp['S'] = 2;
	mp['E'] = 3;
	int k;
	scanf("%d %d %d",&k,&n,&m);
	scanf("%s", buf);
	for(int i=0; i<k; i++){
		buf[i + k] = buf[i];
	}
	k <<= 1;
	int maxt[16] = {};
	for(int i=0; i<16; i++){
		int cnt = 0;
		for(int j=0; j<k; j++){
			if((i >> mp[buf[j]]) & 1){
				cnt++;
				maxt[i] = max(maxt[i], cnt);
			}
			else{
				cnt = 0;
			}
		}
		if(maxt[i] == k) maxt[i] = 1e9;
	}
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			int x; scanf("%d",&x);
			if(x == 0){
				dead[i][j] = 1;
				continue;
			}
			for(int k=0; k<16; k++){
				if(x <= maxt[k]) good[i][j][k] = 1;
			}
		}
	}
	solve();
}

Compilation message (stderr)

virus.cpp: In function 'int main()':
virus.cpp:80:22: warning: array subscript has type 'char' [-Wchar-subscripts]
    if((i >> mp[buf[j]]) & 1){
                      ^
virus.cpp:70:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d %d",&k,&n,&m);
  ~~~~~^~~~~~~~~~~~~~~~~~~~~
virus.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%s", buf);
  ~~~~~^~~~~~~~~~~
virus.cpp:92:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    int x; scanf("%d",&x);
           ~~~~~^~~~~~~~~

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