Submission #544756

#	Time	Username	Problem	Language	Result	Execution time	Memory
544756		rainboy	Viruses (BOI20_viruses)	C11	100 / 100	56 ms	3288 KiB

Viruses

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

#define N	102
#define N_	(N * 2)
#define L	50
#define M	(1 + L)

long long add(long long a, long long b) { return a != -1 && b != -1 && a < LLONG_MAX - b ? a + b : -1; }

int *lj[N_], *lk[N_], lo[N_], *rj[N_], *rk[N_], ro[N_], *oj[N_], oo[N_];

void init() {
	int i;

	for (i = 0; i < N_; i++) {
		lj[i] = (int *) malloc(2 * sizeof *lj[i]);
		lk[i] = (int *) malloc(2 * sizeof *lk[i]);
		rj[i] = (int *) malloc(2 * sizeof *rj[i]);
		rk[i] = (int *) malloc(2 * sizeof *rk[i]);
		oj[i] = (int *) malloc(2 * sizeof *oj[i]);
	}
}

void append1(int **oj, int *oo, int i, int j) {
	int o = oo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		oj[i] = (int *) realloc(oj[i], o * 2 * sizeof *oj[i]);
	oj[i][o] = j;
}

void append2(int **oj, int **ok, int *oo, int i, int j, int k) {
	int o = oo[i]++;

	if (o >= 2 && (o & o - 1) == 0) {
		oj[i] = (int *) realloc(oj[i], o * 2 * sizeof *oj[i]);
		ok[i] = (int *) realloc(ok[i], o * 2 * sizeof *ok[i]);
	}
	oj[i][o] = j, ok[i][o] = k;
}

int tt[1 + M][2]; char bad[1 + M];

int build(int m) {
	static int ff[1 + M], qu[1 + M];
	int n, i, head, cnt;

	n = 2;
	while (m--) {
		int l, a;

		scanf("%d", &l);
		i = 1;
		while (l--) {
			scanf("%d", &a);
			if (!tt[i][a])
				tt[i][a] = n++;
			i = tt[i][a];
		}
		bad[i] = 1;
	}
	tt[0][0] = tt[0][1] = 1;
	head = cnt = 0;
	ff[1] = 0, qu[head + cnt++] = 1;
	while (cnt) {
		int e, a;

		i = qu[cnt--, head++], e = ff[i];
		bad[i] |= bad[e];
		for (a = 0; a < 2; a++) {
			int j = tt[i][a], f = tt[e][a];

			if (j)
				ff[j] = f, qu[head + cnt++] = j;
			else
				tt[i][a] = f;
		}
	}
	return n;
}

long long dd[N_ * M * M];
int iq[1 + N_ * M * M], pq[N_ * M * M], cnt;

int lt(int i, int j) { return dd[i] < dd[j]; }

int p2(int p) {
	return (p *= 2) > cnt ? 0 : (p < cnt && lt(iq[p + 1], iq[p]) ? p + 1 : p);
}

void pq_up(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p / 2) && lt(i, j = iq[q]); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_dn(int i) {
	int p, q, j;

	for (p = pq[i]; (q = p2(p)) && lt(j = iq[q], i); p = q)
		iq[pq[j] = p] = j;
	iq[pq[i] = p] = i;
}

void pq_add_last(int i) {
	iq[pq[i] = ++cnt] = i;
}

int pq_remove_first() {
	int i = iq[1], j = iq[cnt--];

	if (j != i)
		pq[j] = 1, pq_dn(j);
	pq[i] = 0;
	return i;
}

int main() {
	static long long ans[N];
	int n, n_, k, m, i, s, t;

	init();
	scanf("%d%d%d", &n, &k, &m);
	n_ = n;
	while (k--) {
		static int ii[N];
		int cnt, h, i_;

		scanf("%d%d", &i, &cnt);
		for (h = 0; h < cnt; h++)
			scanf("%d", &ii[h]);
		i_ = ii[cnt - 1];
		for (h = cnt - 2; h >= 0; h--) {
			append2(lj, lk, lo, i_, ii[h], n_);
			append2(rj, rk, ro, ii[h], i_, n_);
			i_ = n_++;
		}
		append1(oj, oo, i_, i);
	}
	m = build(m) - 1;
	memset(ans, -1, n * sizeof *ans);
	memset(dd, -1, n_ * m * m * sizeof *dd);
	for (s = 0; s < m; s++) {
		int a;

		if (bad[s + 1])
			continue;
		for (a = 0; a < 2; a++) {
			t = tt[s + 1][a] - 1;
			if (!bad[t + 1]) {
				int u = (a * m + s) * m + t;

				dd[u] = 1, pq_add_last(u);
			}
		}
	}
	while (cnt) {
		int u, v, o, j, k, s_, t_;
		long long d;

		u = pq_remove_first(), i = u / m / m, s = u / m % m, t = u % m;
		if (i < n && s == 0 && (ans[i] == -1 || ans[i] > dd[u]))
			ans[i] = dd[u];
		for (o = oo[i]; o--; ) {
			j = oj[i][o], v = (j * m + s) * m + t, d = dd[u];
			if (d != -1 && (dd[v] == -1 || dd[v] > d)) {
				if (dd[v] == -1)
					pq_add_last(v);
				dd[v] = d, pq_up(v);
			}
		}
		for (o = lo[i]; o--; ) {
			j = lj[i][o], k = lk[i][o];
			for (s_ = 0; s_ < m; s_++) {
				v = (k * m + s_) * m + t, d = add(dd[(j * m + s_) * m + s], dd[u]);
				if (d != -1 && (dd[v] == -1 || dd[v] > d)) {
					if (dd[v] == -1)
						pq_add_last(v);
					dd[v] = d, pq_up(v);
				}
			}
		}
		for (o = ro[i]; o--; ) {
			j = rj[i][o], k = rk[i][o];
			for (t_ = 0; t_ < m; t_++) {
				v = (k * m + s) * m + t_, d = add(dd[u], dd[(j * m + t) * m + t_]);
				if (d != -1 && (dd[v] == -1 || dd[v] > d)) {
					if (dd[v] == -1)
						pq_add_last(v);
					dd[v] = d, pq_up(v);
				}
			}
		}
	}
	for (i = 2; i < n; i++)
		if (ans[i] == -1)
			printf("YES\n");
		else
			printf("NO %lld\n", ans[i]);
	return 0;
}

Compilation message (stderr)

Viruses.c: In function 'append1':
Viruses.c:30:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   30 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Viruses.c: In function 'append2':
Viruses.c:38:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   38 |  if (o >= 2 && (o & o - 1) == 0) {
      |                     ~~^~~
Viruses.c: In function 'build':
Viruses.c:55:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d", &l);
      |   ^~~~~~~~~~~~~~~
Viruses.c:58:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |    scanf("%d", &a);
      |    ^~~~~~~~~~~~~~~
Viruses.c: In function 'main':
Viruses.c:128:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |  scanf("%d%d%d", &n, &k, &m);
      |  ^~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.c:134:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  134 |   scanf("%d%d", &i, &cnt);
      |   ^~~~~~~~~~~~~~~~~~~~~~~
Viruses.c:136:4: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  136 |    scanf("%d", &ii[h]);
      |    ^~~~~~~~~~~~~~~~~~~

• Subtask 1: 11 / 11
• Subtask 2: 14 / 14
• Subtask 3: 25 / 25
• Subtask 4: 32 / 32
• Subtask 5: 18 / 18