제출 #1287385

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1287385		am_aadvik	바이러스 (JOI19_virus)	C++20	6 / 100	2095 ms	11360 KiB

virus

#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];
bool vis[801][801] = { 0 };
vector<bool> s2(800 * 900);
bool check(int i, int j, int n, int m, 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<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<int> res; 
	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 = 1e9, mnc = 0;
	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()) {
			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][nj]) continue;
				if (check(ni, nj, n, m, a[ni][nj]))
					q.push({ ni, nj }), vis[ni][nj] = 1, ++ans;
			}
		}
		if (!ended)
			if (mn > ans) mn = ans, mnc = 1;
			else if (mn == ans) ++mnc;
		memset(vis, 0, sizeof(vis));
		s2[i * m + j] = 1;
	}
	cout << mn << '\n' << mnc * mn;
}

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