제출 #1287511

#제출 시각아이디문제언어결과실행 시간메모리
1287511am_aadvikVirus Experiment (JOI19_virus)C++20
0 / 100
121 ms12364 KiB
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include<random>
#include<chrono>
#include<cstring>
#include<set>
using namespace std;

int di[] = { 1, 0, 0, -1 }, dj[] = { 0, -1, 1, 0 }, mx[20];
vector<bool> s2(800 * 900);
bool check(int i, int j, int n, int m, int val, vector<int> &vis, int q) {
	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 * m + nj] == q) 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<int> wind;
	for (auto& i : s) wind.push_back(((i == 'N') ? 0 : ((i == 'E') ? 1 : ((i == 'W') ? 2 : 3))));
	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);
	for (int j = 0; j < 16; ++j) {
		for (int i = 0; i < k; ++i) {
			int cur = 0;
			while ((i < k) && (j & (1 << wind[i]))) ++i, ++cur;
			mx[j] = max(mx[j], cur);
		}
	}
	for (int i = 0; i < 20; ++i)
		mx[i] += ((mx[i] == k) * 2e5);
	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);
	int mn = 1, mnc = 0;
	vector<int> vis(n * m + m);
	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 * m + j] = i *m + j + 1, ++ans;
		bool ended = 0;
		while (!q.empty()) {
			if (ans > mn) break;
			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[x * m + y]) { 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 * m + nj] == (i * m + j + 1)) continue;
				if (check(ni, nj, n, m, a[ni][nj], vis, i * m + j + 1))
					q.push({ ni, nj }), vis[ni * m + nj] = (i * m + j + 1), ++ans;
			}
		}
		if (!ended)
			if (mn > ans) mn = ans, mnc = 1;
			else if (mn == ans) ++mnc;
		s2[i * m + j] = 1;
	}
	cout << mn << '\n' << mnc * mn;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...