Submission #1287312

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287312		am_aadvik	Virus Experiment (JOI19_virus)	C++20	6 / 100	344 ms	2948 KiB

virus

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;

int c(char i) { return ((i == 'N') ? 0 : ((i == 'E') ? 1 : ((i == 'W') ? 2 : 3))); }
int di[] = { 1, 0, 0, -1 };
int dj[] = { 0, -1, 1, 0 };
bool check(int i, int j, vector<vector<int>>& vis, int n, int m, vector<int> mx, int val) {
	int mask = 0;
	for (int d = 0; d < 4; ++d) {
		int ni = di[d] + i, nj = dj[d] + j;
		if ((ni < 0) || (nj < 0) || (nj >= m) || (ni >= n)) continue;
		if (vis[ni][nj]) mask |= (1 << (3 - d));
	}
	return mx[mask] >= val;
}
int main() {
	int k, n, m; cin >> k >> n >> m;
	string s; cin >> s; s += s, k += k;
	vector<vector<int>> a(n, vector<int>(m));
	for (auto& x : a) for (auto& y : x) cin >> y;
	vector<int> mx(20);
	for (int j = 0; j < 16; ++j) {
		for (int i = 0; i < k; ++i) {
			int cur = 0;
			while ((i < k) && (j & (1 << c(s[i])))) ++i, ++cur;
			mx[j] = max(mx[j], cur);
		}
	}
	for (int i = 0; i < 20; ++i) 
		mx[i] += ((mx[i] == k) * 2e5);
	if ((n * m) <= 2500) {
		vector<int> res;
		vector<vector<int>> vis(n, vector<int>(m, 0));
		for (int i = 0; i < n; ++i)
			for (int j = 0; j < m; ++j) {
				if (a[i][j] == 0) continue;
				vis.assign(n, vector<int>(m, 0));
				queue<pair<int, int>> q;
				q.push({ i, j }), vis[i][j] = 1;
				while (!q.empty()) {
					auto f = q.front(); q.pop();
					int x = f.first, y = f.second;
					for (int d = 0; d < 4; ++d) {
						int ni = di[d] + x, nj = dj[d] + y;
						if ((ni < 0) || (nj < 0) || (nj >= m) || (ni >= n)) continue;
						if ((a[ni][nj] == 0) || vis[ni][nj]) continue;
						if (check(ni, nj, vis, n, m, mx, a[ni][nj])) 
							q.push({ ni, nj }), vis[ni][nj] = 1;
					}
				}
				int ans = 0;
				for (auto& x : vis) for (auto& y : x) ans += y;
				res.push_back(ans);
			}
		int ans = 0;
		sort(res.begin(), res.end());
		for (auto x : res) ans += (x == res[0]);
		cout << res[0] << endl << ans;
	}
}

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