Submission #712361

#	Time	Username	Problem	Language	Result	Execution time	Memory
712361		rainboy	Virus Experiment (JOI19_virus)	C11	6 / 100	290 ms	262144 KiB

virus

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

#define N	800
#define M	800
#define NM	(N * M)
#define LG	20	/* LG = ceil(log2(NM)) */
#define N_	(NM * 4 * (LG + 1) + 1)
#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_[NM], n, m, nm;

int ll[N_], rr[N_], bb[N_]; char has[N_];

int add(int t, int l, int r, int i, int b) {
	static int _ = 1;
	int t_ = _++;

	ll[t_] = ll[t], rr[t_] = rr[t];
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (i < m)
			ll[t_] = add(ll[t_], l, m, i, b);
		else
			rr[t_] = add(rr[t_], m, r, i, b);
		has[t_] = has[ll[t_]] || has[rr[t_]];
	} else
		bb[t_] = b, has[t_] = kk_[i] <= kk[b];
	return t_;
}

int merge(int t1, int t2, int l, int r) {
	if (t1 == 0)
		return t2;
	if (t2 == 0)
		return t1;
	if (r - l > 1) {
		int m = (l + r) / 2;

		ll[t1] = merge(ll[t1], ll[t2], l, m), rr[t1] = merge(rr[t1], rr[t2], m, r);
		has[t1] = has[ll[t1]] || has[rr[t1]];
	} else
		bb[t1] |= bb[t2], has[t1] = kk_[l] <= kk[bb[t1]];
	return t1;
}

int get(int t, int l, int r, int *i_) {
	if (!has[t])
		return t;
	if (r - l > 1) {
		int m = (l + r) / 2;

		if (has[ll[t]])
			ll[t] = get(ll[t], l, m, i_);
		else
			rr[t] = get(rr[t], m, r, i_);
		has[t] = has[ll[t]] || has[rr[t]];
		return ll[t] == 0 && rr[t] == 0 ? 0 : t;
	} else {
		*i_ = l;
		return 0;
	}
}

int ds[NM];

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

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

int ds_[NM], sz[NM], tt[NM], pp[NM];

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

void join_(int i, int j) {
	i = find_(i);
	j = find_(j);
	if (i == j)
		return;
	if (ds_[i] > ds_[j])
		ds_[i] = j, sz[j] += sz[i], tt[j] = merge(tt[j], tt[i], 0, nm);
	else {
		if (ds_[i] == ds_[j])
			ds_[i]--;
		ds_[j] = i, sz[i] += sz[j], tt[i] = merge(tt[i], tt[j], 0, nm);
	}
}

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

	scanf("%d%d%d%s", &l, &n, &m, cc), nm = 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, nm * sizeof *ds);
	memset(ds_, -1, nm * sizeof *ds_);
	for (ij = 0; ij < nm; ij++)
		sz[ij] = 1;
	for (i = 0; i < n; i++)
		for (j = 0; j < m; j++) {
			ij = i * m + j;
			if (kk_[ij] != 0)
				for (g = 0; g < 4; g++) {
					i_ = i + di[g], j_ = j + dj[g], ij_ = i_ * m + j_;
					if (i_ >= 0 && i_ < n && j_ >= 0 && j_ < m && kk_[ij_] != 0)
						tt[ij] = add(tt[ij], 0, nm, ij_, 1 << g);
				}
		}
	cnt = 0;
	for (ij = 0; ij < nm; ij++) {
		pp[ij] = -1, tt[ij] = get(tt[ij], 0, nm, &pp[ij]);
		if (pp[ij] != -1 && !join(ij, pp[ij]))
			qu[cnt++] = ij;
	}
	while (cnt--) {
		ij = find_(qu[cnt]);
		cnt_ = 0;
		ij_ = ij;
		do
			qu_[cnt_++] = ij_;
		while ((ij_ = find_(pp[ij_])) != ij);
		while (cnt_--)
			join_(ij, qu_[cnt_]);
		ij = find_(ij);
		pp[ij] = -1, tt[ij] = get(tt[ij], 0, nm, &pp[ij]);
		if (pp[ij] != -1 && !join(ij, pp[ij]))
			qu[cnt++] = ij;
	}
	s_ = INF, c_ = 0;
	for (ij = 0; ij < nm; ij++)
		if (ds_[ij] < 0 && pp[ij] == -1 && kk_[ij] != 0) {
			if (s_ > sz[ij])
				s_ = sz[ij], c_ = 0;
			if (s_ == sz[ij])
				c_ += sz[ij];
		}
	printf("%d\n", s_);
	printf("%d\n", c_);
	return 0;
}

Compilation message (stderr)

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

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