Submission #721016

#	Time	Username	Problem	Language	Result	Execution time	Memory
721016		Radin_Zahedi2	Virus Experiment (JOI19_virus)	C++17	100 / 100	472 ms	78104 KiB

virus

#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define sz(x) (int)x.size()
#define endl '\n'
const int inf = 1e9;

int m, r, c;
const int R = 8e2 + 5;
const int dire[4][2] = {{-1, 0}, {0, 1}, {0, -1}, {1, 0}};
string s;
int u[R][R];

int give[16];

pair<int, int> bel[R][R];

pair<int, int> par[R][R];
int len[R][R];

int inted(char c) {
	if (c == 'N') {
		return 0;
	}
	if (c == 'E') {
		return 1;
	}
	if (c == 'W') {
		return 2;
	}

	return 3;
}

pair<int, int> get(pair<int, int> u) {
	if (par[u.fi][u.se] == u) {
		return u;
	}

	par[u.fi][u.se] = get(par[u.fi][u.se]);
	return par[u.fi][u.se];
}

void unio(pair<int, int> u, pair<int, int> v) {
	pair<int, int> p1 = get(u), p2 = get(v);
	if (p1 == p2) {
		return;
	}

	if (len[p1.fi][p1.se] < len[p2.fi][p2.se]) {
		swap(p1, p2);
	}


	len[p1.fi][p1.se] += len[p2.fi][p2.se];
	par[p2.fi][p2.se] = p1;
}

void input() {
	cin >> m >> r >> c;
	cin >> s;

	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			cin >> u[i][j];
		}
	}
}

void cregive() {
	for (int mask = 0; mask < 16; mask++) {
		vector<int> inds;
		
		for (int i = 0; i < m; i++) {
			if (!((mask >> inted(s[i])) & 1)) {
				inds.pb(i);
			}
		}

		if (inds.empty()) {
			give[mask] = inf;
			continue;
		}
		
		for (int i = 0; i < sz(inds) - 1; i++) {
			give[mask] = max(give[mask], inds[i + 1] - inds[i] - 1);
		}
		give[mask] = max(give[mask], inds[0] + m - inds.back() - 1);
	}
}

bool can(int x, int y, int x0, int y0) {
	if (!u[x][y]) {
		return false;
	}

	int mask = 0;
	for (int d = 0; d < 4; d++) {
		if (bel[x + dire[d][0]][y + dire[d][1]] == mp(x0, y0)) {
			mask |= (1 << d);
		}
	}

	return (give[mask] >= u[x][y]);
}

pair<int, int> bfs() {
	vector<pair<int, int>> cands[r + 1][c + 1];

	vector<pair<int, int>> q;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (u[i][j]) {
				bel[i][j] = mp(i, j);
				par[i][j] = mp(i, j);
				len[i][j] = 1;

				cands[i][j].pb(mp(i, j));

				q.pb(mp(i, j));
			}
		}
	}

	vector<pair<int, int>> actis;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (u[i][j]) {
				actis.pb(mp(i, j));
			}
		}
	}


	int result;
	for (int m = 1; m <= r * c + 1; m++) {
		bool done = false;
		for (auto p : actis) {
			if (cands[p.fi][p.se].empty()) {
				done = true;
				break;
			}
		}
		if (done) {
			result = m - 1;
			break;
		}


		vector<pair<int, int>> nactis;
		for (auto p : actis) {
			pair<int, int> pc = cands[p.fi][p.se].back();

			if (get(pc) != get(p)) {
				cands[p.fi][p.se].clear();
				unio(pc, p);
				continue;
			}
			else {
				nactis.pb(p);
			}
		}

		actis = nactis;

		for (auto p : actis) {
			pair<int, int> pc = cands[p.fi][p.se].back();
			cands[p.fi][p.se].pop_back();
			int x = pc.fi;
			int y = pc.se;


			for (int d = 0; d < 4; d++) {
				int x2 = x + dire[d][0];
				int y2 = y + dire[d][1];

				if (bel[x2][y2] == p) {
					continue;
				}

				
				bel[x][y] = mp(0, 0);
				bool bef = can(x2, y2, p.fi, p.se);
				bel[x][y] = p;
				bool now = can(x2, y2, p.fi, p.se);

				if (!bef && now) {
					cands[p.fi][p.se].pb(mp(x2, y2));
				}
			}
		}
	}


	int t = 0;
	for (auto p : actis) {
		if (cands[p.fi][p.se].empty()) {
			t++;
		}
	}

	return mp(result, t);
}

void solve() {
	cregive();

	pair<int, int> ans = bfs();

	cout << ans.fi << endl << ans.fi * ans.se;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);


	input();

	solve();

	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'std::pair<int, int> bfs()':
virus.cpp:138:6: warning: 'result' may be used uninitialized in this function [-Wmaybe-uninitialized]
  138 |  int result;
      |      ^~~~~~

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