Submission #797410

#	Time	Username	Problem	Language	Result	Execution time	Memory
797410		ymm	Virus Experiment (JOI19_virus)	C++17	100 / 100	367 ms	131212 KiB

virus

#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (l); --x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 100'010;
const int M = 810;
int mx[16];
int val[M][M];
int n, m, d;
string s;

pii constexpr dir[] = {
	{-1, 0},
	{0, -1},
	{1, 0},
	{0, 1},
};

bool isin(int i, int j) { return 0 <= i && i < n && 0 <= j && j < m; }

namespace dsu {
	struct comp {
		vector<pii> nodes;
		vector<pii> adj;
		comp *par;
		int col;
		int dfsvis;
		bool bad;
	} comps[M][M];
	int cmpcol[M][M];


	void add(comp *c, int i, int j) {
		if (val[i][j] == 0)
			return;
		int msk = 0;
		Loop (k,0,4) {
			auto [x, y] = dir[k];
			if (isin(i+x, j+y) && cmpcol[i+x][j+y] == c->col)
				msk ^= (1 << k);
		}
		if (mx[msk] >= val[i][j])
			c->adj.emplace_back(i, j);
	}
	void addadj(comp *c, int i, int j) {
		Loop (k,0,4) {
			auto [x, y] = dir[k];
			if (isin(i+x, j+y))
				add(c, i+x, j+y);
		}
	}

	comp *rt(comp *c) { return c->par? (c->par = rt(c->par)): c; }
	void unite(comp *v, comp *u) {
		v = rt(v);
		u = rt(u);
		assert(v != u);
		if (v->nodes.size() < u->nodes.size())
			swap(v, u);
		v->nodes.insert(v->nodes.end(), u->nodes.begin(), u->nodes.end());
		for (auto [i, j] : u->nodes)
			cmpcol[i][j] = v->col;
		for (auto [i, j] : u->nodes)
			addadj(v, i, j);
		vector<pii>().swap(u->nodes);
		vector<pii>().swap(u->adj);
		u->par = v;
	}
	comp *rt(int i, int j) { return rt(&comps[i][j]); }
	comp *rt(pii p) { return rt(&comps[p.first][p.second]); }

	void init() {
		int cnt = 0;
		Loop (i,0,n) Loop (j,0,m) {
			if (val[i][j] == 0)
				continue;
			comp *v = &comps[i][j];
			v->par = 0;
			v->col = ++cnt;
			cmpcol[i][j] = v->col;
			v->nodes = {pii{i, j}};
			v->dfsvis = 0;
			v->bad = 0;
			addadj(v, i, j);
		}
	}
}

void mkmx()
{
	int msk[256];
	msk['N'] = 1<<0;
	msk['W'] = 1<<1;
	msk['S'] = 1<<2;
	msk['E'] = 1<<3;
	Loop (dard,0,16) {
		int lst = 0;
		Loop (i,0,2*d) {
			int x = msk[s[i>=d?i-d:i]];
			if (!(dard & x)) {
				mx[dard] = max<int>(mx[dard], i-lst);
				lst = i+1;
			}
		}
		mx[dard] = max<int>(mx[dard], 2*d-lst);
	}
}

void dfs(dsu::comp *c, int t)
{
	vector<dsu::comp *> st = {c};
	c->dfsvis = t;
	for (;;) {
		auto v = st.back();
		if (v->adj.empty()) {
			st.pop_back();
			break;
		}
		auto u = dsu::rt(v->adj.back());
		v->adj.pop_back();
		if (v == u)
			continue;
		if (u->dfsvis && u->dfsvis != t)
			break;
		if (u->dfsvis == t) {
			while (st.back() != dsu::rt(u)) {
				auto x = st.back(); st.pop_back();
				auto y = st.back(); st.pop_back();
				dsu::unite(x, y);
				st.push_back(dsu::rt(x));
			}
		} else {
			st.push_back(u);
			u->dfsvis = t;
		}
	}
	for (auto v : st)
		v->bad = 1;
}

int main()
{
	cin.tie(0) -> sync_with_stdio(false);
	cin >> d >> n >> m >> s;
	Loop (i,0,n) Loop (j,0,m) {
		cin >> val[i][j];
		val[i][j] = min(val[i][j], d);
	}
	mkmx();
	dsu::init();
	int cnt = 0;
	Loop (i,0,n) Loop (j,0,m) {
		if (val[i][j] == 0)
			continue;
		auto c = dsu::rt(i, j);
		if (c->dfsvis)
			continue;
		dfs(c, ++cnt);
	}
	int ans = 1e9, ansc = 0;
	Loop (i,0,n) Loop (j,0,m) {
		if (val[i][j] == 0)
			continue;
		auto c = dsu::rt(i, j);
		if (c->bad)
			continue;
		if (ans > c->nodes.size()) {
			ans = c->nodes.size();
			ansc = 0;
		}
		if (ans == c->nodes.size())
			++ansc;
	}
	cout << ans << '\n' << ansc << '\n';
}

Compilation message (stderr)

virus.cpp: In function 'void mkmx()':
virus.cpp:102:29: warning: array subscript has type 'char' [-Wchar-subscripts]
  102 |    int x = msk[s[i>=d?i-d:i]];
      |                             ^
virus.cpp: In function 'int main()':
virus.cpp:170:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  170 |   if (ans > c->nodes.size()) {
      |       ~~~~^~~~~~~~~~~~~~~~~
virus.cpp:174:11: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |   if (ans == c->nodes.size())
      |       ~~~~^~~~~~~~~~~~~~~~~~

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