Submission #448351

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
448351	2021-07-29T18:58:28 Z	cheissmart	Virus Experiment (JOI19_virus)	C++17	100 / 100	630 ms	102972 KB

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.0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	17036 KB	Output is correct
2	Correct	291 ms	74888 KB	Output is correct
3	Correct	269 ms	79028 KB	Output is correct
4	Correct	267 ms	79104 KB	Output is correct
5	Correct	226 ms	62760 KB	Output is correct
6	Correct	15 ms	28236 KB	Output is correct
7	Correct	319 ms	79284 KB	Output is correct
8	Correct	123 ms	41136 KB	Output is correct

Subtask #2

6.0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	9 ms	15820 KB	Output is correct
2	Correct	22 ms	18216 KB	Output is correct
3	Correct	39 ms	18236 KB	Output is correct
4	Correct	23 ms	18220 KB	Output is correct
5	Correct	39 ms	18152 KB	Output is correct
6	Correct	43 ms	18692 KB	Output is correct
7	Correct	10 ms	15820 KB	Output is correct
8	Correct	40 ms	18500 KB	Output is correct
9	Correct	11 ms	16716 KB	Output is correct
10	Correct	23 ms	18196 KB	Output is correct
11	Correct	11 ms	16844 KB	Output is correct
12	Correct	12 ms	16760 KB	Output is correct
13	Correct	40 ms	18540 KB	Output is correct
14	Correct	39 ms	18552 KB	Output is correct
15	Correct	47 ms	18536 KB	Output is correct
16	Correct	41 ms	18564 KB	Output is correct
17	Correct	28 ms	17464 KB	Output is correct
18	Correct	12 ms	16916 KB	Output is correct
19	Correct	41 ms	18332 KB	Output is correct

Subtask #3

80.0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	17 ms	17036 KB	Output is correct
2	Correct	291 ms	74888 KB	Output is correct
3	Correct	269 ms	79028 KB	Output is correct
4	Correct	267 ms	79104 KB	Output is correct
5	Correct	226 ms	62760 KB	Output is correct
6	Correct	15 ms	28236 KB	Output is correct
7	Correct	319 ms	79284 KB	Output is correct
8	Correct	123 ms	41136 KB	Output is correct
9	Correct	9 ms	15820 KB	Output is correct
10	Correct	22 ms	18216 KB	Output is correct
11	Correct	39 ms	18236 KB	Output is correct
12	Correct	23 ms	18220 KB	Output is correct
13	Correct	39 ms	18152 KB	Output is correct
14	Correct	43 ms	18692 KB	Output is correct
15	Correct	10 ms	15820 KB	Output is correct
16	Correct	40 ms	18500 KB	Output is correct
17	Correct	11 ms	16716 KB	Output is correct
18	Correct	23 ms	18196 KB	Output is correct
19	Correct	11 ms	16844 KB	Output is correct
20	Correct	12 ms	16760 KB	Output is correct
21	Correct	40 ms	18540 KB	Output is correct
22	Correct	39 ms	18552 KB	Output is correct
23	Correct	47 ms	18536 KB	Output is correct
24	Correct	41 ms	18564 KB	Output is correct
25	Correct	28 ms	17464 KB	Output is correct
26	Correct	12 ms	16916 KB	Output is correct
27	Correct	41 ms	18332 KB	Output is correct
28	Correct	479 ms	98164 KB	Output is correct
29	Correct	527 ms	102972 KB	Output is correct
30	Correct	301 ms	81776 KB	Output is correct
31	Correct	400 ms	83976 KB	Output is correct
32	Correct	369 ms	85100 KB	Output is correct
33	Correct	277 ms	77868 KB	Output is correct
34	Correct	614 ms	96916 KB	Output is correct
35	Correct	331 ms	70108 KB	Output is correct
36	Correct	487 ms	84360 KB	Output is correct
37	Correct	543 ms	96460 KB	Output is correct
38	Correct	431 ms	90120 KB	Output is correct
39	Correct	409 ms	81252 KB	Output is correct
40	Correct	437 ms	81760 KB	Output is correct
41	Correct	265 ms	79656 KB	Output is correct
42	Correct	630 ms	92332 KB	Output is correct
43	Correct	360 ms	90792 KB	Output is correct
44	Correct	125 ms	41188 KB	Output is correct