Submission #712405

#	Time	Username	Problem	Language	Result	Execution time	Memory
712405		rainboy	Virus Experiment (JOI19_virus)	C11	100 / 100	390 ms	89588 KiB

virus

#include <stdio.h>
#include <string.h>

#define N	800
#define M	800
#define N_	(N * M * 2)
#define L	100000
#define B	(1 << 4)
#define INF	0x3f3f3f3f

int max(int a, int b) { return a > b ? a : b; }

int di[] = { -1, 1, 0, 0 };
int dj[] = { 0, 0, -1, 1 };
char map[] = "NSWE";

int kk[B], kk_[N_], n, m, n_;

int next[N_ * 8], xx[N_ * 8], mem[N_ * 8], cnt;

void init() {
	int o;
	
	for (o = 0; o < N_ * 8; o++)
		mem[cnt++] = o;
}

int node(int x) {
	int o = mem[--cnt];

	next[o] = -1, xx[o] = x;
	return o++;
}

void free_(int o) {
	mem[cnt++] = o;
}

int ds[N_];

int find(int u) {
	return ds[u] < 0 ? u : (ds[u] = find(ds[u]));
}

int join(int u, int v) {
	u = find(u);
	v = find(v);
	if (u == v)
		return 0;
	if (ds[u] > ds[v])
		ds[u] = v;
	else {
		if (ds[u] == ds[v])
			ds[u]--;
		ds[v] = u;
	}
	return 1;
}

int ds_[N_], sz[N_], head[N_], tail[N_], head_[N_], tail_[N_], pp[N_];

int find_(int u) {
	return ds_[u] < 0 ? u : (ds_[u] = find_(ds_[u]));
}

void add_(int u, int o) {
	if (head_[u] == -1)
		head_[u] = tail_[u] = o;
	else
		next[tail_[u]] = o, tail_[u] = o;
}

int check(int u, int v, int w) {
	int g, i, i_, j, j_, t, bu, bv;

	i = w / m, j = w % m;
	if (kk_[w] == 0)
		return 0;
	t = find_(w);
	if (t == u || t == v)
		return 0;
	bu = 0, bv = 0;
	for (g = 0; g < 4; g++) {
		i_ = i - di[g], j_ = j - dj[g], t = find_(i_ * m + j_);
		if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m) {
			if (t == u)
				bu |= 1 << g;
			else if (t == v)
				bv |= 1 << g;
		}
	}
	return kk_[w] > kk[bv] && kk_[w] <= kk[bu | bv];
}

char visited[N][M];

void merge(int u, int v) {
	int o, g, i, i_, j, j_, u_, v_;

	sz[v] += sz[u];
	for (o = head_[u]; o != -1; o = next[o])
		free_(o);
	for (o = head[u]; o != -1; o = next[o]) {
		u_ = xx[o], i = u_ / m, j = u_ % m;
		for (g = 0; g < 4; g++) {
			i_ = i + di[g], j_ = j + dj[g], v_ = i_ * m + j_;
			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && !visited[i_][j_] && check(u, v, v_))
				visited[i_][j_] = 1, add_(v, node(v_));
		}
	}
	for (o = head[u]; o != -1; o = next[o]) {
		u_ = xx[o], i = u_ / m, j = u_ % m;
		for (g = 0; g < 4; g++) {
			i_ = i + di[g], j_ = j + dj[g], v_ = i_ * m + j_;
			if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m)
				visited[i_][j_] = 0;
		}
	}
	next[tail[v]] = head[u], tail[v] = tail[u];
}

void join_(int u, int v) {
	u = find_(u);
	v = find_(v);
	if (u == v)
		return;
	if (ds_[u] > ds_[v])
		merge(u, v), ds_[u] = v;
	else {
		if (ds_[u] == ds_[v])
			ds_[u]--;
		merge(v, u), ds_[v] = u;
	}
}

int get(int u) {
	int o, v;

	while ((o = head_[u]) != -1) {
		v = find_(xx[o]);
		if (v != u)
			return v;
		free_(o);
		if (next[o] != -1)
			head_[u] = next[o];
		else
			head_[u] = tail_[u] = -1;
	}
	return -1;
}

int main() {
	static char cc[L + 1];
	static int qu[N_], qu_[N_];
	int l, g, h, i, i_, j, j_, u, v, b, k, cnt, cnt_, s_, c_;

	init();
	scanf("%d%d%d%s", &l, &n, &m, cc), n_ = n * m;
	for (h = 0; h < l; h++)
		cc[h] = (strchr(map, cc[h]) - map) ^ 1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++)
			scanf("%d", &kk_[i * m + j]);
	for (b = 0; b < B; b++) {
		k = 0;
		for (h = 0; h < l; h++)
			k = (b & 1 << cc[h]) != 0 ? k + 1 : 0;
		if (k == l)
			kk[b] = INF;
		else {
			kk[b] = 0;
			for (h = 0; h < l; h++)
				kk[b] = max(kk[b], k = (b & 1 << cc[h]) != 0 ? k + 1 : 0);
		}
	}
	memset(ds, -1, n_ * sizeof *ds);
	memset(ds_, -1, n_ * sizeof *ds_);
	for (u = 0; u < n_; u++)
		sz[u] = 1, head[u] = tail[u] = node(u), head_[u] = tail_[u] = -1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			u = i * m + j;
			if (kk_[u] != 0)
				for (g = 0; g < 4; g++) {
					i_ = i + di[g], j_ = j + dj[g], v = i_ * m + j_;
					if (check(u, -1, v))
						add_(u, node(v));
				}
		}
	cnt = 0;
	for (u = 0; u < n_; u++)
		if ((pp[u] = get(u)) != -1 && !join(u, pp[u]))
			qu[cnt++] = u;
	while (cnt--) {
		u = find_(qu[cnt]);
		cnt_ = 0;
		v = u;
		do
			qu_[cnt_++] = v;
		while ((v = find_(pp[v])) != u);
		while (cnt_--)
			join_(u, qu_[cnt_]);
		u = find_(u);
		if ((pp[u] = get(u)) != -1 && !join(u, pp[u]))
			qu[cnt++] = u;
	}
	s_ = INF, c_ = 0;
	for (u = 0; u < n_; u++)
		if (ds_[u] < 0 && pp[u] == -1 && kk_[u] != 0) {
			if (s_ > sz[u])
				s_ = sz[u], c_ = 0;
			if (s_ == sz[u])
				c_ += sz[u];
		}
	printf("%d\n", s_);
	printf("%d\n", c_);
	return 0;
}

Compilation message (stderr)

virus.c: In function 'main':
virus.c:158:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  158 |  scanf("%d%d%d%s", &l, &n, &m, cc), n_ = n * m;
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
virus.c:163:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  163 |    scanf("%d", &kk_[i * m + j]);
      |    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~

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