Submission #200649

#	Time	Username	Problem	Language	Result	Execution time	Memory
200649		tincamatei	Virus Experiment (JOI19_virus)	C++14	6 / 100	283 ms	4728 KiB

virus

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 800;

int U[1+MAX_N][1+MAX_N];
bool viz[1+MAX_N+1][1+MAX_N+1];

int force[1<<4];

int chToDir[128];
char dirToCh[4 + 1] = "SENW";
int dl[] = {1, 0, -1, 0};
int dc[] = {0, 1,  0,-1};

void init() {
	for(int i = 0; i < 4; ++i)
		chToDir[dirToCh[i]] = i;
}


bool getInfected(int l, int c) {
	int mask = 0;
	for(int i = 0; i < 4; ++i) {
		int ln = l + dl[i];
		int cn = c + dc[i];
		if(viz[ln][cn])
			mask = mask | (1 << i); // Mark the opposite direction
	}

	return U[l][c] != 0 && U[l][c] <= force[mask];
}

vector<pair<int, int> > comp;

void dfs(int l, int c) {
	viz[l][c] = true;

	comp.push_back({l, c});

	for(int i = 0; i < 4; ++i) {
		int ln = l + dl[i];
		int cn = c + dc[i];
		if(!viz[ln][cn] && getInfected(ln, cn))
			dfs(ln, cn);
	}
}

void clearDfs() {
	for(auto it: comp)
		viz[it.first][it.second] = false;
	comp.clear();
}

int main() {
	int M, R, C;
	string D;

	init();

	cin >> M >> R >> C >> D;
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j)
			cin >> U[i][j];

	for(int mask = 1; mask < (1 << 4); ++mask) {
		int cnt = 0, best = 0;
		for(int _i = 0; _i < 2 * M; ++_i) {
			int i = _i % M;

			if(mask & (1 << chToDir[D[i]]))
				++cnt;
			else
				cnt = 0;

			best = max(best, cnt);
		}

		if(best >= M)
			best = 100001;
		force[mask] = best;
	}

	int rez = R * C + 1, cntRez = 0;
	for(int i = 1; i <= R; ++i)
		for(int j = 1; j <= C; ++j) {
			clearDfs();
			if(U[i][j] != 0) {
				dfs(i, j);
				if(comp.size() < rez) {
					rez = comp.size();
					cntRez = 1;
				} else if(comp.size() == rez)
					++cntRez;
			}
		}

	printf("%d\n%d", rez, cntRez);

	return 0;
}

Compilation message (stderr)

virus.cpp: In function 'void init()':
virus.cpp:19:21: warning: array subscript has type 'char' [-Wchar-subscripts]
   chToDir[dirToCh[i]] = i;
                     ^
virus.cpp: In function 'int main()':
virus.cpp:72:32: warning: array subscript has type 'char' [-Wchar-subscripts]
    if(mask & (1 << chToDir[D[i]]))
                                ^
virus.cpp:91:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if(comp.size() < rez) {
        ~~~~~~~~~~~~^~~~~
virus.cpp:94:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     } else if(comp.size() == rez)
               ~~~~~~~~~~~~^~~~~~

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