oj.uz

Submission #544756

# Submission time Handle Problem Language Result Execution time Memory
544756 2022-04-02T16:29:11 Z rainboy Viruses (BOI20_viruses) C
100 / 100
 56 ms 3288 KB 
#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

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.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct

Subtask #2
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 2516 KB Output is correct
4 Correct 1 ms 2388 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 2 ms 3028 KB Output is correct
7 Correct 2 ms 3028 KB Output is correct
8 Correct 2 ms 2900 KB Output is correct
9 Correct 1 ms 2004 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 852 KB Output is correct
12 Correct 1 ms 596 KB Output is correct
13 Correct 1 ms 1236 KB Output is correct
14 Correct 1 ms 852 KB Output is correct
15 Correct 1 ms 980 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 1108 KB Output is correct
18 Correct 1 ms 852 KB Output is correct
19 Correct 1 ms 980 KB Output is correct
20 Correct 1 ms 980 KB Output is correct
21 Correct 1 ms 1108 KB Output is correct
22 Correct 1 ms 724 KB Output is correct
23 Correct 1 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2516 KB Output is correct
2 Correct 1 ms 2388 KB Output is correct
3 Correct 2 ms 3156 KB Output is correct
4 Correct 2 ms 3028 KB Output is correct
5 Correct 2 ms 3028 KB Output is correct
6 Correct 2 ms 2900 KB Output is correct
7 Correct 1 ms 2004 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 0 ms 340 KB Output is correct
17 Correct 0 ms 336 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 336 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 0 ms 352 KB Output is correct
24 Correct 1 ms 468 KB Output is correct
25 Correct 6 ms 1748 KB Output is correct
26 Correct 1 ms 1364 KB Output is correct
27 Correct 56 ms 3212 KB Output is correct
28 Correct 3 ms 3156 KB Output is correct
29 Correct 45 ms 3032 KB Output is correct
30 Correct 42 ms 2920 KB Output is correct
31 Correct 5 ms 2772 KB Output is correct
32 Correct 3 ms 3156 KB Output is correct
33 Correct 2 ms 3288 KB Output is correct
34 Correct 42 ms 2900 KB Output is correct

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 1 ms 340 KB Output is correct
26 Correct 0 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 1 ms 336 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 0 ms 340 KB Output is correct
31 Correct 0 ms 336 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 0 ms 340 KB Output is correct
34 Correct 0 ms 336 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 0 ms 352 KB Output is correct
38 Correct 1 ms 468 KB Output is correct
39 Correct 0 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 1 ms 336 KB Output is correct
42 Correct 1 ms 336 KB Output is correct
43 Correct 0 ms 340 KB Output is correct
44 Correct 0 ms 336 KB Output is correct
45 Correct 1 ms 340 KB Output is correct
46 Correct 0 ms 340 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 1 ms 340 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 0 ms 344 KB Output is correct
51 Correct 0 ms 344 KB Output is correct
52 Correct 1 ms 340 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 1 ms 468 KB Output is correct
55 Correct 1 ms 340 KB Output is correct

Subtask #5
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 0 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 0 ms 340 KB Output is correct
12 Correct 0 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 0 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 0 ms 340 KB Output is correct
18 Correct 0 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 2 ms 2516 KB Output is correct
22 Correct 1 ms 2388 KB Output is correct
23 Correct 2 ms 3156 KB Output is correct
24 Correct 2 ms 3028 KB Output is correct
25 Correct 2 ms 3028 KB Output is correct
26 Correct 2 ms 2900 KB Output is correct
27 Correct 1 ms 2004 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 852 KB Output is correct
30 Correct 1 ms 596 KB Output is correct
31 Correct 1 ms 1236 KB Output is correct
32 Correct 1 ms 852 KB Output is correct
33 Correct 1 ms 980 KB Output is correct
34 Correct 1 ms 468 KB Output is correct
35 Correct 1 ms 1108 KB Output is correct
36 Correct 1 ms 852 KB Output is correct
37 Correct 1 ms 980 KB Output is correct
38 Correct 1 ms 980 KB Output is correct
39 Correct 1 ms 1108 KB Output is correct
40 Correct 1 ms 724 KB Output is correct
41 Correct 1 ms 340 KB Output is correct
42 Correct 0 ms 340 KB Output is correct
43 Correct 0 ms 340 KB Output is correct
44 Correct 0 ms 340 KB Output is correct
45 Correct 0 ms 340 KB Output is correct
46 Correct 1 ms 340 KB Output is correct
47 Correct 0 ms 340 KB Output is correct
48 Correct 0 ms 340 KB Output is correct
49 Correct 1 ms 336 KB Output is correct
50 Correct 0 ms 340 KB Output is correct
51 Correct 0 ms 340 KB Output is correct
52 Correct 0 ms 336 KB Output is correct
53 Correct 1 ms 340 KB Output is correct
54 Correct 0 ms 340 KB Output is correct
55 Correct 0 ms 336 KB Output is correct
56 Correct 1 ms 340 KB Output is correct
57 Correct 1 ms 340 KB Output is correct
58 Correct 0 ms 352 KB Output is correct
59 Correct 1 ms 468 KB Output is correct
60 Correct 6 ms 1748 KB Output is correct
61 Correct 1 ms 1364 KB Output is correct
62 Correct 56 ms 3212 KB Output is correct
63 Correct 3 ms 3156 KB Output is correct
64 Correct 45 ms 3032 KB Output is correct
65 Correct 42 ms 2920 KB Output is correct
66 Correct 5 ms 2772 KB Output is correct
67 Correct 3 ms 3156 KB Output is correct
68 Correct 2 ms 3288 KB Output is correct
69 Correct 42 ms 2900 KB Output is correct
70 Correct 0 ms 340 KB Output is correct
71 Correct 1 ms 340 KB Output is correct
72 Correct 1 ms 336 KB Output is correct
73 Correct 1 ms 336 KB Output is correct
74 Correct 0 ms 340 KB Output is correct
75 Correct 0 ms 336 KB Output is correct
76 Correct 1 ms 340 KB Output is correct
77 Correct 0 ms 340 KB Output is correct
78 Correct 0 ms 340 KB Output is correct
79 Correct 1 ms 340 KB Output is correct
80 Correct 1 ms 340 KB Output is correct
81 Correct 0 ms 344 KB Output is correct
82 Correct 0 ms 344 KB Output is correct
83 Correct 1 ms 340 KB Output is correct
84 Correct 1 ms 340 KB Output is correct
85 Correct 1 ms 468 KB Output is correct
86 Correct 1 ms 340 KB Output is correct
87 Correct 5 ms 1364 KB Output is correct
88 Correct 1 ms 340 KB Output is correct
89 Correct 1 ms 340 KB Output is correct
90 Correct 1 ms 724 KB Output is correct
91 Correct 1 ms 596 KB Output is correct
92 Correct 17 ms 1588 KB Output is correct
93 Correct 12 ms 1340 KB Output is correct
94 Correct 1 ms 1228 KB Output is correct
95 Correct 1 ms 852 KB Output is correct
96 Correct 1 ms 1108 KB Output is correct
97 Correct 4 ms 1236 KB Output is correct
98 Correct 1 ms 1496 KB Output is correct
99 Correct 8 ms 2260 KB Output is correct
100 Correct 1 ms 1236 KB Output is correct
101 Correct 2 ms 1364 KB Output is correct
102 Correct 30 ms 2260 KB Output is correct
103 Correct 3 ms 2388 KB Output is correct
104 Correct 8 ms 2532 KB Output is correct
105 Correct 1 ms 724 KB Output is correct
106 Correct 16 ms 2740 KB Output is correct
107 Correct 15 ms 2644 KB Output is correct