Submission #503184

#	Time	Username	Problem	Language	Result	Execution time	Memory
503184		amunduzbaev	Virus Experiment (JOI19_virus)	C++14	0 / 100	2 ms	460 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, k <<= 1;
	vector<int> mx(1 << 4, 0), cur(1 << 4, 0);
	for(int i=0;i<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]++, mx[mask] = max(mx[mask], cur[mask]);
			else cur[mask] = 0;
		}
	}
	
	//~ for(int i=0;i<16;i++){
		//~ for(int j=0;j<4;j++) cout<<(i>>j&1);
		//~ cout<<" : "; 
		//~ cout<<mn[i]<<"\n";
	//~ }
	
	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];
			a[i][j] = min(a[i][j], k/2);
			if(a[i][j]) ord.push_back(i * m + j);
		}
	}
	int res = 1e9, cnt = 0;
	shuffle(ord.begin(), ord.end(), rng);
	vector<vector<int>> t(n, vector<int>(m, -1)), 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)) return false;
		if(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]) continue;
				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<<cnt * res<<"\n"<<res<<"\n";
}

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