Submission #1287371

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287371		am_aadvik	Virus Experiment (JOI19_virus)	C++20	6 / 100	2093 ms	16460 KiB

virus

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include<random>
#include<chrono>
#include<cstring>
#include<set>
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 vis[801][810] = { 0 };
bool check(int i, int j, 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() {
	ios_base::sync_with_stdio(false), cin.tie(NULL);
	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;
	for (auto& x : a) for (auto& y : x) y = ((y == 0) ? 1e9 : 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);
	vector<int> res; 
	set<pair<int, int>> s2;
	vector<pair<int, int>> arr;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < m; ++j)
			arr.push_back({ i, j });
	unsigned seed = chrono::system_clock::now().time_since_epoch().count();
	default_random_engine rng(seed);
	shuffle(arr.begin(), arr.end(), rng);
	for (auto& cur : arr) {
		int i = cur.first, j = cur.second, ans = 0;
		if (a[i][j] == 1e9) continue;
		queue<pair<int, int>> q;
		q.push({ i, j }), vis[i][j] = 1, ++ans;
		bool ended = 0;
		while (!q.empty()) {
			auto f = q.front(); q.pop();
			int x = f.first, y = f.second;
			//if we alr did all calc for this node, then thats better
			if (s2.find({ x, y }) != s2.end()) {ended = 1; break;} 
			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 (vis[ni][nj]) continue;
				if (check(ni, nj, n, m, mx, a[ni][nj]))
					q.push({ ni, nj }), vis[ni][nj] = 1, ++ans;
			}
		}
		if (!ended)
			res.push_back(ans), 
			s2.insert({ i, j });
		memset(vis, 0, sizeof(vis));
	}
	int ans = 0;
	sort(res.begin(), res.end());
	for (auto x : res) ans += (x == res[0]);
	cout << res[0] << endl << ans * res[0];
}

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