제출 #489519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489519		Haruto810198	바이러스 (JOI19_virus)	C++17	6 / 100	2076 ms	5976 KiB

virus

#include <bits/stdc++.h>

using namespace std;

#define int long long
#define double long double

#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())

#define vi vector<int>
#define pii pair<int, int>

#define F first
#define S second

#define pb push_back
#define eb emplace_back
#define mkp make_pair

const int INF = INT_MAX;
const int LNF = INF*INF;
const int MOD = 1000000007;

const int dx[4] = {-1, 1, 0, 0};
const int dy[4] = {0, 0, -1, 1};
// N, S, W, E (from)

int m;
vi str;
int r, c;
int def[810][810];
// immune -> def = INF
int len[16]; // len[mask] = longest substring
// continuous -> len = INF - 1

bool vis[810][810];
vector<pii> vised;

int res_min, res_cnt;

void bfs(int sx, int sy){
	
	vector<pii> qu;
	
	vis[sx][sy] = 1;
	vised.eb(sx, sy);
	FOR(i, 0, 3, 1){
		qu.eb(sx + dx[i], sy + dy[i]);
	}
	
	while(!qu.empty()){
		// check if v is not infected
		int vx = qu.back().F;
		int vy = qu.back().S;
		qu.pop_back();
		if(!(1 <= vx and vx <= r and 1 <= vy and vy <= c)) continue;
		if(vis[vx][vy]) continue;
		
		// check if v can be infected
		int mask = 0;
		FOR(i, 0, 3, 1){
			int ix = vx + dx[i], iy = vy + dy[i];
			if(vis[ix][iy]) mask += (1<<i);
		}
		
		// infect v
		if(def[vx][vy] <= len[mask]){
			vis[vx][vy] = 1;
			vised.eb(vx, vy);
			FOR(i, 0, 3, 1){
				qu.eb(vx + dx[i], vy + dy[i]);
			}
		}
	}
	
	int sz = szof(vised);
	if(sz < res_min){
		res_min = sz;
		res_cnt = 1;
	}
	else if(sz == res_min){
		res_cnt++;
	}
	
	//cerr<<"bfs("<<sx<<", "<<sy<<") = "<<viscnt<<endl;
	
	for(pii v : vised){
		vis[v.F][v.S] = 0;
	}
	vised.clear();

}

signed main(){
	
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	cin>>m>>r>>c;
	FOR(i, 1, m, 1){
		char ch;
		cin>>ch;
		if(ch == 'N') str.pb(0);
		if(ch == 'S') str.pb(1);
		if(ch == 'W') str.pb(2);
		if(ch == 'E') str.pb(3);
	}
	
	FOR(i, 0, r+1, 1){
		FOR(j, 0, c+1, 1){
			def[i][j] = INF;
		}
	}

	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			cin>>def[i][j];
			if(def[i][j] == 0) def[i][j] = INF;
		}
	}
	
	// find len[]
	FOR(i, 0, m-1, 1){
		str.pb(str[i]);
	}
	
	FOR(mask, 0, 15, 1){
		int cur = 0;
		for(int i : str){
			if(mask & (1<<i)) cur++;
			else cur = 0;
			len[mask] = max(len[mask], cur);
		}
		if(len[mask] == szof(str)) len[mask] = INF - 1;
	}
	
	res_min = INF;
	FOR(i, 1, r, 1){
		FOR(j, 1, c, 1){
			if(def[i][j] < INF) bfs(i, j);
		}
	}

	cout<<res_min<<'\n'<<res_cnt<<'\n';
	
	return 0;

}

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