Submission #489540

#	Time	Username	Problem	Language	Result	Execution time	Memory
489540		8e7	Virus Experiment (JOI19_virus)	C++17	0 / 100	2 ms	972 KiB

virus

//Challenge: Accepted
#include <iostream>
#include <algorithm>
#include <vector>
#include <utility>
#include <queue>
using namespace std;
void debug(){cout << endl;}
template<class T, class ...U> void debug(T a, U ... b){cout << a << " ", debug(b...);}
template<class T> void pary (T l, T r) {
	while (l != r) cout << *l << " ", l++;
	cout << endl;
}
#define ll long long
#define maxn 805
#define pii pair<int, int>
#define ff first
#define ss second
#define io ios_base::sync_with_stdio(0);cin.tie(0);
const int inf = 1<<30;
bool poss[maxn][maxn][16];
bool done[maxn][maxn], vis[maxn][maxn], col[maxn][maxn], inq[maxn][maxn];
int ans[maxn][maxn];
int u[maxn][maxn], ds[100005], dt[100005];
int dir[4][2] = {{-1, 0}, {0, 1}, {1, 0}, {0, -1}}; // NESW
int r, c;
inline bool in(int x, int y){return x >= 0 && x < r && y >= 0 && y < c;}
bool con(int x, int y) {
	int mask = 0;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (in(dx, dy)) mask += col[dx][dy] ? (1<<i) : 0;
	}
	return poss[x][y][mask];
}
int pnt = 0, lstx = 0, lsty = 0;
vector<pii> ne;

int dfs(int x, int y) {
	vis[x][y] = 1;
	pnt++;
	for (int i = 0;i < 4;i++) {
		int dx = x + dir[i][0], dy = y + dir[i][1];
		if (!in(dx, dy)) continue;
		col[x][y] = 1;
		if (con(dx, dy)) {
			if (done[dx][dy]) {
				ans[x][y] = 1<<30;
				done[x][y] = 1;
				return 2;
			} else if (vis[dx][dy]) {
				lstx = dx, lsty = dy;
				ne.push_back({x, y});
				return 1;	
			} else {
				col[x][y] = 0;
				int ret = dfs(dx, dy);
				if (ret == 2) {
					done[x][y] = 1, ans[x][y] = 1<<30;
					return 2;
				} else if (ret == 1) {
					col[x][y] = 1;
					ne.push_back({x, y});
					if (x == lstx && y == lsty) {
						return 0;	
					} else {
						return 1;
					}
				} else {
					vis[x][y] = 0;
					return 0;
				}
			}
		}
	}
	ans[x][y] = 1;
	done[x][y] = 1;
	lstx = x, lsty = y;
	return 2;	
}
int main() {
	io
	int m;
	cin >> m >> r >> c;
	string D;
	cin >> D;
	for (int i = 0;i < m;i++) ds[i] = (D[i] == 'N' ? 0 : (D[i] == 'E' ? 1 : (D[i] == 'S' ? 2 : 3)));
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) cin >> u[i][j];
	}
	for (int ti = 0;ti < 16;ti++) {
		int ma = 0, cur = 0, tot = 0, pref = 0, suf = 0;
		for (int i = 0;i < m;i++) {
			if (ti & (1<<ds[i])) {
				dt[i] = 1;
			} else {
				ma = max(ma, cur);
				cur = 0;
				dt[i] = 0;
			}
			cur += dt[i];
			tot += dt[i];
		}
		if (tot == m) {
			ma = 1<<30;	
		} else {
			for (int i = 0;i < m;i++) {
				if (!dt[i]) {
					pref = i;
					break;
				}
			}
			for (int i = m - 1;i >= 0;i--) {
				if (!dt[i]) {
					suf = m - 1 - i;
					break;
				}
			}
			ma = max(ma, pref + suf);
		}
		//debug(ma);
		for (int i = 0;i < r;i++) {
			for (int j = 0;j < c;j++) {
				poss[i][j][ti] = u[i][j] <= ma;
				if (u[i][j] == 0) poss[i][j][ti] = 0;
			}
		}
	}
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) {
			if (!u[i][j]) continue;
			if (!done[i][j]) {
				queue<pii> que;
				vector<pii> comp;
				que.push({i, j});
				comp.push_back({i, j});
				bool f = 0;
				while (que.size()) {
					pii cur = que.front();que.pop();
					inq[cur.ff][cur.ss] = 0;
					/*
					for (auto p:comp) {
						cout << p.ff << "," << p.ss << " ";
					}
					cout << endl;
					*/
					ne.clear();
					int val = dfs(cur.ff, cur.ss);
					/*
					debug(cur.ff, cur.ss, val);
					for (auto p:ne) {
						cout << p.ff << "," << p.ss << " ";
					}
					cout << endl;
					debug();	
					*/
					if (val != 2) {
						if (val == 0) {
							for (auto p:comp) col[p.ff][p.ss] = 0;
							comp = ne;
						} else {
							comp.insert(comp.end(), ne.begin(), ne.end());
						}
						for (auto p:ne) {
							for (int k = 0;k < 4;k++) {
								int dx = p.ff + dir[k][0], dy = p.ss + dir[k][1];
								if (!in(dx, dy)) continue;
								if (!col[dx][dy] && con(dx, dy) && !inq[dx][dy]) {
									que.push({dx, dy});
									inq[dx][dy] = 1;
								}
							}
						}
					} else {
						f = 1;
						for (auto p:comp) {
							done[p.ff][p.ss] = 1;
							ans[p.ff][p.ss] = inf;
						}
						while (que.size()) {
							pii p = que.front();que.pop();
							done[p.ff][p.ss] = 1;
							ans[p.ff][p.ss] = inf;
						}
						break;
					}
				}
				if (f) continue;
				int siz = comp.size();
				//debug(7122, i, j, siz);
				for (auto p:comp) {
					ans[p.ff][p.ss] = siz;
					done[p.ff][p.ss] = 1;
				}
			}
		}
	}
	int out = 1<<30, outn = 0;
	for (int i = 0;i < r;i++) {
		for (int j = 0;j < c;j++) {
			if (u[i][j]) {
				//debug(i, j, lef[i][j], rig[i][j]);
				if (ans[i][j] < out) out = ans[i][j], outn = 1;
				else if (ans[i][j] == out) outn++;
			}
		}
	}
	cout << out << "\n" << outn << "\n";
}
/*

7 3 4
EEEWWWE
1 1 0 1
1 0 1 3
1 1 1 1
*/

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