Submission #718451

#	Time	Username	Problem	Language	Result	Execution time	Memory
718451		Radin_Zahedi2	Virus Experiment (JOI19_virus)	C++17	0 / 100	5 ms	980 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> par[R][R];

int res = 0;

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

	return 3;
}

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 (par[x + dire[d][0]][y + dire[d][1]] == mp(x0, y0)) {
			mask |= (1 << d);
		}
	}

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

vector<pair<int, int>> bfs() {
	bool acti[r + 1][c + 1];
	for (int i = 0; i <= r; i++) {
		for (int j = 0; j <= c; j++) {
			acti[i][j] = false;
		}
	}

	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]) {
				acti[i][j] = true;
				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 (acti[i][j]) {		
				actis.pb(mp(i, j));
			}
		}
	}

	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;
				cout << p.fi << ' ' << p.se << endl;
				break;
			}
		}
		if (done) {
			res = m - 1;
			break;
		}


		vector<pair<int, int>> 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;


			int parx = par[x][y].fi;
			int pary = par[x][y].se;

			if (acti[parx][pary]) {
				acti[p.fi][p.se] = false;
				cands[p.fi][p.se].clear();
				cout << "		" << p.fi << ' ' << p.se << ' ' << x << ' ' << y << ' ' << parx << ' ' << pary << endl;
				continue;
			}
		}

		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;


			int parx = par[x][y].fi;
			int pary = par[x][y].se;


			cout << x << ' '<< y << ' ' << p.fi << ' ' << p.se << ' ' << can(x, y, p.fi, p.se) << endl;
			for (int d = 0; d < 4; d++) {
				int x2 = x + dire[d][0];
				int y2 = y + dire[d][1];

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

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

				if (!bef && now) {
					cands[p.fi][p.se].pb(mp(x2, y2));
					//cout << "	" << p.fi << ' ' << p.se <<< ' '<< x2 << ' '<< y2 << endl;
				}

				if (x == 4 && y == 4) {
					cout << "	" << bef << ' ' << now << ' ' << par[x][y].fi << ' ' << x2 << ' ' << y2 << endl;
				}
			}

			par[x][y] = p;
			nactis.pb(p);
		}
	}


	vector<pair<int, int>> ans;
	for (int i = 1; i <= r; i++) {
		for (int j = 1; j <= c; j++) {
			if (cands[i][j].empty() && acti[i][j]) {
				ans.pb(mp(i, j));
			}
		}
	}

	return ans;
}
/*
int calc(int x0, int y0) {
	for (int i = 1; i <= r; i++) 
		for (int j = 1; j <= c; j++) {
			par[i][j] = mp(0, 0);
		}
	}

	vector<pair<int, int>> vec;
	vec.pb(mp(x0, y0));
	par[x0][y0] = mp(x0, y0);

	int m = 0;
	while (!vec.empty()) {
		int x = vec.back().fi;
		int y = vec.back().se;
		
		vec.pop_back();
		m++;

		for (int d = 0; d < 4; d++) {
			int x2 = x + dire[d][0], y2 = y + dire[d][1];
			if (par[x2][y2] != mp(x0, y0)) {
				if (can(x2, y2, x0, y0)) {
					vec.pb(mp(x2, y2));
					par[x2][y2] = mp(x0, y0);
				}
			}
		}
	}

	return m;
}*/

void solve() {
	cregive();

	vector<pair<int, int>> cands = bfs();
//	int m = calc(cands.fi, cands.se);
//	int m = have[cands.fi][cands.se];

	cout << res << endl << res * sz(cands);
}

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::vector<std::pair<int, int> > bfs()':
virus.cpp:159:8: warning: unused variable 'parx' [-Wunused-variable]
  159 |    int parx = par[x][y].fi;
      |        ^~~~
virus.cpp:160:8: warning: unused variable 'pary' [-Wunused-variable]
  160 |    int pary = par[x][y].se;
      |        ^~~~

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