제출 #503224

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
503224		amunduzbaev	바이러스 (JOI19_virus)	C++14	100 / 100	875 ms	18408 KiB

virus

#include "bits/stdc++.h"
using namespace std;
 
#define ar array
//~ #define int long long

signed main(){
	mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios::sync_with_stdio(0); cin.tie(0);
	
	int k, n, m; cin>>k>>n>>m;
	string s; cin>>s;
	s += s;
	vector<int> mx(1 << 4, 0), cur(1 << 4, 0);
	for(int i=0;i<2*k;i++){
		int c = 0;
		if(s[i] == 'N') c = 0;
		if(s[i] == 'E') c = 1;
		if(s[i] == 'S') c = 2;
		if(s[i] == 'W') c = 3;
		
		for(int mask=0;mask<16;mask++){
			if(mask >> c & 1) cur[mask]++;
			else cur[mask] = 0;
			mx[mask] = max(mx[mask], cur[mask]);
		}
	}
	
	for(int i=0;i<16;i++){
		if(mx[i] >= k) mx[i] = 1e9 + 7;
	}
	
	vector<vector<int>> a(n, vector<int>(m));
	vector<int> ord;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
			if(a[i][j]) ord.push_back(i * m + j);
		}
	}
	shuffle(ord.begin(), ord.end(), rng);
	
	int res = 1e9, cnt = 0;
	vector<vector<int>> t(n, vector<int>(m)), used(n, vector<int>(m));
	int tt = 0;
	for(auto x : ord) t[x/m][x%m] = ++tt;
	int ch[4][2] = {
		{-1, 0},
		{0, 1},
		{1, 0},
		{0, -1}
	};
	
	auto check = [&](int i, int j){
		if(!(0 <= i && i < n && 0 <= j && j < m) || a[i][j] == 0) return false;
		int tot = 0;
		for(int t=0;t<4;t++){
			int x = i + ch[t][0], y = j + ch[t][1];
			if(0 <= x && x < n && 0 <= y && y < m && used[x][y]) tot |= (1 << t);
		}
		
		return (mx[tot] >= a[i][j]);
	};
	
	for(auto x : ord){
		int i = x/m, j = x%m;
		vector<int> tot; tot.push_back(x);
		queue<int> qq; qq.push(x);
		used[i][j] = 1; 
		bool flag = 1;
		while(!qq.empty() && flag){
			int x = qq.front() / m, y = qq.front() % m; qq.pop();
			for(int k=0;k<4;k++){
				int r = x + ch[k][0], c = y + ch[k][1];
				if(check(r, c) && !used[r][c]) {
					used[r][c] = 1, qq.push(r * m + c);
					tot.push_back(r * m + c);
					if(t[r][c] < t[i][j]) { flag = 0; break; }
				}
			}
		}
		
		for(auto x : tot) used[x/m][x%m] = 0;
		if(!flag) continue;
		int sz = (int)tot.size();
		if(sz < res) res = sz, cnt = 0;
		cnt += (sz == res);
	}
	
	cout<<res<<"\n"<<cnt * res<<"\n";
}

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