Submission #174562

#	Time	Username	Problem	Language	Result	Execution time	Memory
174562		Bruteforceman	Virus Experiment (JOI19_virus)	C++11	100 / 100	1680 ms	123896 KiB

virus

#include <bits/stdc++.h>
using namespace std;
#define count cnt
string s;
const int dx[] = {0, 0, 1, -1};
const int dy[] = {1, -1, 0, 0};
const char dir[] = {'E', 'W', 'S', 'N'};
 
typedef pair <int, int> pii;
 
bool done[805][805];
bool vis[805][805];
bool infect[1 << 4][805][805];
int a[805][805];
int ans[805][805];
int optimal;
int count;
int r, c;
unordered_set <int> reachable[805][805];
int par[801 * 801];

int root(int x) {
	if(par[x] == x) return x;
	return par[x] = root(par[x]);
}
void join(int x, int y) {
	x = root(x);
	y = root(y);
	if(x != y) {
		par[x] = y;
	}
}
inline int convert(int i, int j) {
	return j + i * c;
}
inline bool inside(int x, int y) {
	return (0 <= x && x < r) && (0 <= y && y < c);
}
inline int check(int i, int j) {
	int mask = 0;
	for(int p = 0; p < 4; p++) {
		int x = i + dx[p];
		int y = j + dy[p];
		if(inside(x, y) && vis[x][y]) {
			mask |= 1 << p;
		}
	}
	return infect[mask][i][j];
}
void solve(int x, int y) {
	queue <pii> Q;
	vector <pii> reach; 
	vis[x][y] = true;
	Q.push(pii(x, y));
	bool bad = false;
	while(!Q.empty()) {
		int p = Q.front().first;
		int q = Q.front().second;
		Q.pop();
		reach.push_back(pii(p, q));
		if(bad) continue;
		for(int i = 0; i < 4; i++) {
			int nx = p + dx[i];
			int ny = q + dy[i];
			if(!inside(nx, ny) || vis[nx][ny]) continue;
			if(check(nx, ny)) {
				int anc = root(convert(nx, ny));
				nx = (anc / c);
				ny = (anc % c);
				if(done[nx][ny]) {
					if(ans[nx][ny] == optimal && reachable[nx][ny].find(convert(x, y)) != reachable[nx][ny].end()) {
						++count;
						ans[x][y] = ans[nx][ny];
						join(convert(x, y), anc);
					} else {
						ans[x][y] = INT_MAX;
					}
					bad = true;
					break;
				}
				Q.push(pii(nx, ny));
				vis[nx][ny] = true;
			}
		}
	}
	for(auto i : reach) {
		vis[i.first][i.second] = false;
	}
	done[x][y] = true;
	if(!bad) {
		ans[x][y] = reach.size();
		if(optimal == ans[x][y]) {
			++count;
		} else if (ans[x][y] < optimal) {
			optimal = ans[x][y];
			count = 1;
		}
  		reachable[x][y].max_load_factor(0.25); //updated !
		for(auto i : reach) {
			reachable[x][y].insert(convert(i.first, i.second));
		}
	}
}
int main() {
	ios_base :: sync_with_stdio(false);
	cin.tie(0);
	
	int n;
	cin >> n >> r >> c;
	cin >> s;
	s = s + s;
	for(int x = 0; x < r; x++) {
		for(int y = 0; y < c; y++) {
			cin >> a[x][y];
		}
	}
	for(int i = 0; i < (1 << 4); i++) {
		set <char> allow;
		for(int j = 0; j < 4; j++) {
			if((i >> j) & 1) {
				allow.insert(dir[j]);
			}
		}
		int opt = 0;
		int cur = 0;
		for(int j = 0; j < (int) s.size(); j++) {
			int num;
			if(allow.find(s[j]) == allow.end()) {
				num = 0;
			} else num = 1;
			if(num == 0) cur = 0;
			else {
				cur += 1;
				opt = max(opt, cur);
			}
		}
		if(opt == n + n) {
			opt = INT_MAX;
		} 
		for(int x = 0; x < r; x++) {
			for(int y = 0; y < c; y++) {
				if(a[x][y] > 0 && a[x][y] <= opt) {
					infect[i][x][y] = true;
				}
			}
		}
	}
	optimal = INT_MAX;
	count = 0;
	vector <pii> order;
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			par[convert(i, j)] = convert(i, j); 
			order.push_back(pii(i, j));
		}
	}
	random_shuffle(order.begin(), order.end());
	for(auto pt : order) {
		if(a[pt.first][pt.second] == 0) continue;
		solve(pt.first, pt.second);
	}
	cout << optimal << endl;
	cout << count << endl;
	return 0;
}

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