Submission #448351

#	Time	Username	Problem	Language	Result	Execution time	Memory
448351		cheissmart	Virus Experiment (JOI19_virus)	C++17	100 / 100	630 ms	102972 KiB

virus

#include <bits/stdc++.h>
#define IO_OP std::ios::sync_with_stdio(0); std::cin.tie(0);
#define F first
#define S second
#define V vector
#define PB push_back
#define MP make_pair
#define EB emplace_back
#define ALL(v) (v).begin(), (v).end()

using namespace std;

typedef long long ll;
typedef pair<int, int> pi;
typedef V<int> vi;

string to_string(char c) { return string(1, c); }
string to_string(bool b) { return b?"true":"false"; }
string to_string(const char* s) { return string(s); }
string to_string(string s) { return s; }
string to_string(V<bool> v) {
	string res;
	for(int i=0;i<(int)v.size();i++) res+=char('0'+v[i]);
	return res;
}
template<class T1, class T2> string to_string(pair<T1, T2> p) {return "(" + to_string(p.F) + ", " + to_string(p.S) + ")";}
template<size_t S> string to_string(bitset<S> b) {
	string res;
	for(int i=0;i<S;i++) res+=char('0'+b[i]);
	return res;
}
template<class T> string to_string(T v) {
    bool f=1;
    string res;
    for(auto x:v){
		if(!f) res+=' ';
		f=0; res+=to_string(x);
	}
    return res;
}



string _reset = "\u001b[0m", _yellow = "\u001b[33m", _bold = "\u001b[1m";
void DBG() { cerr << "]" << _reset << endl; }
template<class H, class...T> void DBG(H h, T ...t) {
	cerr << to_string(h);
	if(sizeof ...(t)) cerr << ", ";
	DBG(t...);
}
#ifdef CHEISSMART
#define debug(...) cerr << _yellow << _bold << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__)
#else
#define debug(...)
#endif

const int INF = 1e9 + 7, N = 808;

string DIR = "NESW";
int di[] = {-1, 0, 1, 0}, dj[] = {0, 1, 0, -1};

int a[N][N];
int r, c, m;
bool can[N][N][1 << 4];

int get_len(vi& v) {
	int mx = 0, cur = 0;
	for(int i:v) {
		if(i == 0) {
			mx = max(mx, cur);
			cur = 0;
		} else {
			cur++;
		}
	}
	mx = max(mx, cur);
	return mx;
}

pi p[N][N];
V<pi> rp[N][N];
bool dead[N][N];
pi who[N][N];

pi& P(pi u) { return p[u.F][u.S]; }
V<pi>& RP(pi u) { return rp[u.F][u.S]; }
pi& WHO(pi u) { return who[u.F][u.S]; }
bool& DEAD(pi u) { 
	u = WHO(P(u));
	return dead[u.F][u.S];
}

void unite(pi u, pi v) {
	u = P(u), v = P(v);
	if(u == v) return;
	debug(u.F, u.S, v.F, v.S);
	pi new_rep = WHO(v);
	if(RP(u).size() > RP(v).size()) swap(u, v);
	for(pi e:RP(u)) {
		RP(v).PB(e);
		P(e) = v;
	}
	RP(u).clear();
	WHO(v) = new_rep;
}

int vis[N][N], cnt = 0;

bool valid(int i, int j) {
	return 0 <= i && i < r && 0 <= j && j < c;
}

pair<pi, int> BFS(pi s) {
	assert(WHO(P(s)) == s);
	cnt++;
	int res = 0;
	queue<pi> q;
	pi x = {-1, -1};
	auto add = [&] (int i, int j) {
		assert(p[i][j] == P(s));
		assert(vis[i][j] != cnt);
		vis[i][j] = cnt;
		res++;
		q.push(MP(i, j));
	};
	auto check = [&] (int i, int j) {
		int mask = 0;
		for(int k = 0; k < 4; k++) {
			int ii = i + di[k], jj = j + dj[k];
			if(valid(ii, jj) && vis[ii][jj] == cnt) {
				mask |= 1 << k;
			}
		}
		return can[i][j][mask];
	};

	add(s.F, s.S);
	while(q.size()) {
		auto [i, j] = q.front(); q.pop();
		for(int k = 0; k < 4; k++) {
			int ii = i + di[k], jj = j + dj[k];
			if(valid(ii, jj) && vis[ii][jj] != cnt) {
				if(check(ii, jj)) {
					if(s == MP(2, 3)) {
						debug(ii, jj);
					}
					if(p[ii][jj] == P(s)) {
						add(ii, jj);
					} else {
						x = {ii, jj};
					}
				}
			}
		}
	}
	return {x, res};
}

signed main()
{
	IO_OP;

	string ds;
	cin >> m >> r >> c >> ds;

	vi d;
	for(char _:ds)
		d.PB(int(find(ALL(DIR), _) - DIR.begin()));

	for(int i = 0; i < r; i++)
		for(int j = 0; j < c; j++)
			cin >> a[i][j];

	for(int mask = 0; mask < (1 << 4); mask++) {
		vi td;
		for(int i:d) td.PB(mask >> i & 1);
		int len = INF;
		if(find(ALL(td), 0) != td.end()) {
			for(int i = 0; i < int(d.size()); i++)
				td.PB(td[i]);
			len = get_len(td);
		}
		for(int i = 0; i < r; i++) {
			for(int j = 0; j < c; j++) if(a[i][j] && a[i][j] <= len) {
				can[i][j][mask] = true;
			}
		}
	}
	for(int i = 0; i < r; i++) {
		for(int j = 0; j < c; j++) {
			who[i][j] = p[i][j] = {i, j};
			rp[i][j].EB(i, j);
		}
	}

	int ans = INF, cnt = 0;
	for(int _ = 0; _ < 100; _++) {
		V<pair<pi, pi>> todo;
		for(int i = 0; i < r; i++) for(int j = 0; j < c; j++) if(a[i][j]) {
			if(WHO(P(MP(i, j))) == MP(i, j) && !DEAD(MP(i, j))) {
				pair<pi, int> x = BFS({i, j});
				if(x.F.F == -1) { // no new
					if(x.S < ans) ans = x.S, cnt = x.S;
					else if(x.S == ans) cnt += x.S;
					debug(i, j, x, RP(MP(i, j)));
					DEAD(MP(i, j)) = true;
				} else {
					todo.EB(MP(i, j), x.F);
				}
			}
		}
		if(todo.empty()) break;
		for(auto [u, v] : todo)
			unite(u, v);
	}

	cout << ans << '\n' << cnt << '\n';

}

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