oj.uz

Submission #504032

# Submission time Handle Problem Language Result Execution time Memory
504032 2022-01-09T14:33:36 Z rainboy Wells (CEOI21_wells) C
80 / 100
 2946 ms 219380 KB 
/* https://hsin.hr/ceoi/competition/ceoi2021_day2_editorial.pdf */
#include <stdio.h>
#include <stdlib.h>

#define N	1500000
#define SMALL	10000
#define MD	1000000007
#define INF	0x3f3f3f3f

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

int pp2[N + 1];

void init() {
	int i;

	pp2[0] = 1;
	for (i = 1; i <= N; i++)
		pp2[i] = pp2[i - 1] * 2 % MD;
}

int mem[(N - 1) * 2], *ptr = mem;
int *ej[N], eo[N], pp[N], n, k; char type[N];

int i_, l;
int ii[N]; char path[N];

void dfs1(int p, int i, int d) {
	int o;

	pp[i] = p;
	d++;
	if (l < d)
		l = d, i_ = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs1(i, j, d);
	}
}

int gg[N], dd[N], hh[N];

void dfs2(int p, int i, int g, int d) {
	int o;

	gg[i] = g, dd[i] = d, hh[i] = 0;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j]) {
			dfs2(i, j, g, d + 1);
			hh[i] = max(hh[i], hh[j] + 1);
		}
	}
}

int dfs3(int p, int i, int d) {
	int o, x;

	if (d == 0 || type[i] == -1)
		return 1;
	x = 1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			x = (long long) x * dfs3(i, j, d - 1) % MD;
	}
	return (x + 1) % MD;
}

int cc[N], dp[N], dq[N], dr[N];

int dfs4(int p, int i) {
	int o, p1, p2;

	dp[i] = -INF, dq[i] = 0, dr[i] = -1, p1 = p2 = -INF;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p && !path[j] && type[j] == 1) {
			if (!dfs4(i, j))
				return 0;
			dp[i] = max(dp[i], dp[j]);
			if (p1 < dp[j])
				p2 = p1, p1 = dp[j];
			else if (p2 < dp[j])
				p2 = dp[j];
			if (cc[i] == 0 && dq[i] + dq[j] + 1 >= k - 1)
				return 0;
			dq[i] = max(dq[i], dq[j] + 1);
			if (dr[j] != -1)
				dr[i] = dr[j] + 1;
		}
	}
	if (cc[i] == 1)
		dp[i] = hh[i], dq[i] = -1, dr[i] = 0;
	else if (p2 != -INF && dr[i] * 2 <= k - 1 && dr[i] * 2 + p1 + p2 >= k - 1)
		return 0;
	return 1;
}

char bad[N];

void mark_bad() {
	static int aa[N + 1];
	int g, r, i, d;

	for (g = 0; g < l; g++)
		if (type[ii[g]] == 1) {
			int lower, upper;

			lower = g + 1, upper = min(g * 2, k - 1);
			if (lower <= upper)
				aa[lower]++, aa[upper + 1]--;
			lower = max(g * 2 - l + 1, l - k), upper = g - 1;
			if (lower <= upper) {
				lower %= k, upper %= k;
				aa[lower]++, aa[upper + 1]--;
				if (lower > upper)
					aa[0]++;
			}
		}
	for (r = 1; r < k; r++)
		aa[r] += aa[r - 1];
	for (r = 0; r < k; r++)
		if (aa[r])
			bad[r] = 1;
	for (i = 0; i < n; i++)
		if (!path[i] && type[i] == 1) {
			int r1, r2;

			g = gg[i], d = dd[i];
			r1 = (g + d) % k, r2 = (g - d % k + k) % k;
			if (r1 != r2) {
				if (g >= r1 && g <= (l - 1 - r1) / k * k + r1)
					bad[r1] = 1;
				if (g >= r2 && g <= (l - 1 - r2) / k * k + r2)
					bad[r2] = 1;
			}
		}
}

int yes, ans;

void try(int r) {
	int g, gl, gr, i, d, x;

	if (bad[r])
		return;
	gl = r, gr = (l - 1 - r) / k * k + r;
	for (i = 0; i < n; i++) {
		g = gg[i], d = dd[i];
		if (path[i])
			cc[i] = g % k == r ? 1 : 0;
		else if (type[i] == 1)
			cc[i] = g >= gl ? ((g + d) % k == r ? 1 : 0) : ((g - d % k + k) % k == r ? 1 : 0);
	}
	x = 1;
	for (i = 0; i < n; i++)
		if (!path[i] && type[i] == 0 && (path[pp[i]] || type[pp[i]] == 1)) {
			g = gg[i], d = dd[i];
			if (g + dd[i] + hh[i] >= k - 1) {
				if (g < gl)
					x = (long long) x * dfs3(pp[i], i, k - 1 - (g + dd[i])) % MD;
			} else {
				if (g > gr)
					x = (long long) x * dfs3(pp[i], i, k - 1 - (l - 1 - g + dd[i])) % MD;
			}
		}
	for (g = 0; g < l; g++)
		if (type[ii[g]] == 1 && !dfs4(-1, ii[g]))
			return;
	yes = 1, ans = (ans + x) % MD;
}

int main() {
	static int uu[N - 1], vv[N - 1];
	int g, h, i, j, u, v, d, r, deep;

	init();
	scanf("%d%d", &n, &k);
	if (k == 2) {
		printf("YES\n");
		printf("2\n");
		return 0;
	}
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		uu[h] = i, vv[h] = j;
		eo[i]++, eo[j]++;
	}
	for (i = 0; i < n; i++) {
		ej[i] = ptr, ptr += eo[i];
		eo[i] = 0;
	}
	for (h = 0; h < n - 1; h++) {
		i = uu[h], j = vv[h];
		ej[i][eo[i]++] = j, ej[j][eo[j]++] = i;
	}
	i_ = -1, l = -1, dfs1(-1, 0, 0), u = i_;
	i_ = -1, l = -1, dfs1(-1, u, 0), v = i_;
	if (l < k) {
		printf("YES\n");
		printf("%d\n", pp2[n]);
		return 0;
	}
	for (i = v, d = l - 1; i != u; i = pp[i], d--)
		path[ii[d] = i] = 1;
	path[ii[0] = u] = 1;
	for (g = 0; g < l; g++)
		dfs2(-1, ii[g], g, 0);
	for (i = 0; i < n; i++) {
		g = gg[i];
		if (max(g, l - 1 - g) + dd[i] + hh[i] < k - 1)
			type[i] = -1;
		else if (min(g, l - 1 - g) + dd[i] + hh[i] >= k - 1)
			type[i] = 1;
		else
			type[i] = 0;
	}
	mark_bad();
	yes = 0, ans = 0;
	deep = 0;
	for (i = 0; i < n; i++)
		if (dd[i] * 2 >= k - 1) {
			deep = 1;
			break;
		}
	if (deep || n <= SMALL)
		for (r = 0; r < k; r++)
			try(r);
	else {
		for (r = 0; r < k; r++)
			if (!bad[r]) {
				printf("YES\n");
				printf("0\n");
				return 0;
			}
		printf("NO\n");
		printf("0\n");
		return 0;
	}
	if (yes) {
		printf("YES\n");
		for (i = 0; i < n; i++)
			if (!path[i] && type[i] == -1)
				ans = ans * 2 % MD;
		printf("%d\n", ans);
	} else {
		printf("NO\n");
		printf("0\n");
	}
	return 0;
}

Compilation message

wells.c: In function 'main':
wells.c:185:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  185 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
wells.c:192:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6092 KB Output is correct
2 Correct 10 ms 6220 KB Output is correct
3 Correct 9 ms 6220 KB Output is correct
4 Correct 9 ms 6208 KB Output is correct
5 Correct 7 ms 6256 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 8 ms 6220 KB Output is correct
8 Correct 8 ms 6184 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 9 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 8 ms 6120 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6272 KB Output is correct
15 Correct 8 ms 6272 KB Output is correct
16 Correct 9 ms 6220 KB Output is correct
17 Correct 8 ms 6204 KB Output is correct
18 Correct 9 ms 6168 KB Output is correct
19 Correct 8 ms 6220 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6220 KB Output is correct
22 Correct 8 ms 6212 KB Output is correct
23 Correct 8 ms 6220 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 7 ms 6220 KB Output is correct
26 Correct 8 ms 6220 KB Output is correct
27 Correct 8 ms 6220 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6248 KB Output is correct
30 Correct 7 ms 6220 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct
32 Correct 8 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6220 KB Output is correct
35 Correct 10 ms 6276 KB Output is correct
36 Correct 9 ms 6220 KB Output is correct
37 Correct 10 ms 6224 KB Output is correct
38 Correct 8 ms 6212 KB Output is correct
39 Correct 9 ms 6220 KB Output is correct
40 Correct 9 ms 6264 KB Output is correct
41 Correct 8 ms 6248 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 8 ms 6220 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 9 ms 6180 KB Output is correct
46 Correct 8 ms 6220 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6220 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6220 KB Output is correct
51 Correct 8 ms 6244 KB Output is correct
52 Correct 10 ms 6220 KB Output is correct
53 Correct 8 ms 6220 KB Output is correct
54 Correct 8 ms 6220 KB Output is correct
55 Correct 9 ms 6220 KB Output is correct
56 Correct 8 ms 6220 KB Output is correct
57 Correct 8 ms 6268 KB Output is correct
58 Correct 8 ms 6236 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6092 KB Output is correct
2 Correct 10 ms 6220 KB Output is correct
3 Correct 9 ms 6220 KB Output is correct
4 Correct 9 ms 6208 KB Output is correct
5 Correct 7 ms 6256 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 8 ms 6220 KB Output is correct
8 Correct 8 ms 6184 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 9 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 8 ms 6120 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6272 KB Output is correct
15 Correct 8 ms 6272 KB Output is correct
16 Correct 9 ms 6220 KB Output is correct
17 Correct 8 ms 6204 KB Output is correct
18 Correct 9 ms 6168 KB Output is correct
19 Correct 8 ms 6220 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6220 KB Output is correct
22 Correct 8 ms 6212 KB Output is correct
23 Correct 8 ms 6220 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 7 ms 6220 KB Output is correct
26 Correct 8 ms 6220 KB Output is correct
27 Correct 8 ms 6220 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6248 KB Output is correct
30 Correct 7 ms 6220 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct
32 Correct 8 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6220 KB Output is correct
35 Correct 10 ms 6276 KB Output is correct
36 Correct 9 ms 6220 KB Output is correct
37 Correct 10 ms 6224 KB Output is correct
38 Correct 8 ms 6212 KB Output is correct
39 Correct 9 ms 6220 KB Output is correct
40 Correct 9 ms 6264 KB Output is correct
41 Correct 8 ms 6248 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 8 ms 6220 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 9 ms 6180 KB Output is correct
46 Correct 8 ms 6220 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6220 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6220 KB Output is correct
51 Correct 8 ms 6244 KB Output is correct
52 Correct 10 ms 6220 KB Output is correct
53 Correct 8 ms 6220 KB Output is correct
54 Correct 8 ms 6220 KB Output is correct
55 Correct 9 ms 6220 KB Output is correct
56 Correct 8 ms 6220 KB Output is correct
57 Correct 8 ms 6268 KB Output is correct
58 Correct 8 ms 6236 KB Output is correct
59 Correct 8 ms 6220 KB Output is correct
60 Correct 11 ms 6604 KB Output is correct
61 Correct 10 ms 6424 KB Output is correct
62 Correct 9 ms 6580 KB Output is correct
63 Correct 11 ms 6988 KB Output is correct
64 Correct 11 ms 7372 KB Output is correct
65 Correct 12 ms 6860 KB Output is correct
66 Correct 11 ms 6860 KB Output is correct
67 Correct 50 ms 7396 KB Output is correct
68 Correct 9 ms 6604 KB Output is correct
69 Correct 11 ms 6348 KB Output is correct
70 Correct 11 ms 6656 KB Output is correct
71 Correct 10 ms 6596 KB Output is correct
72 Correct 10 ms 6600 KB Output is correct
73 Correct 66 ms 6604 KB Output is correct
74 Correct 260 ms 7072 KB Output is correct
75 Correct 99 ms 6860 KB Output is correct
76 Correct 14 ms 6988 KB Output is correct
77 Correct 11 ms 6476 KB Output is correct
78 Correct 22 ms 6488 KB Output is correct
79 Correct 12 ms 6476 KB Output is correct
80 Correct 171 ms 6824 KB Output is correct
81 Correct 199 ms 6916 KB Output is correct
82 Correct 91 ms 6724 KB Output is correct
83 Correct 106 ms 7048 KB Output is correct
84 Correct 11 ms 6732 KB Output is correct
85 Correct 261 ms 7096 KB Output is correct
86 Correct 13 ms 6860 KB Output is correct
87 Correct 12 ms 7148 KB Output is correct
88 Correct 12 ms 7112 KB Output is correct
89 Correct 11 ms 6988 KB Output is correct
90 Correct 40 ms 6628 KB Output is correct
91 Correct 81 ms 7056 KB Output is correct
92 Correct 239 ms 7272 KB Output is correct
93 Correct 24 ms 7056 KB Output is correct
94 Correct 12 ms 6860 KB Output is correct
95 Correct 22 ms 6776 KB Output is correct
96 Correct 12 ms 6604 KB Output is correct
97 Correct 68 ms 6604 KB Output is correct
98 Correct 81 ms 6696 KB Output is correct
99 Correct 69 ms 6604 KB Output is correct
100 Correct 199 ms 6980 KB Output is correct
101 Correct 37 ms 6944 KB Output is correct
102 Correct 77 ms 7004 KB Output is correct
103 Correct 14 ms 6988 KB Output is correct
104 Correct 11 ms 7016 KB Output is correct
105 Correct 14 ms 7064 KB Output is correct
106 Correct 12 ms 6828 KB Output is correct
107 Correct 12 ms 7252 KB Output is correct
108 Correct 12 ms 6940 KB Output is correct
109 Correct 13 ms 6912 KB Output is correct
110 Correct 16 ms 7128 KB Output is correct
111 Correct 11 ms 6988 KB Output is correct
112 Correct 11 ms 7180 KB Output is correct
113 Correct 11 ms 6988 KB Output is correct
114 Correct 11 ms 7080 KB Output is correct
115 Correct 10 ms 6860 KB Output is correct
116 Correct 11 ms 7204 KB Output is correct
117 Correct 11 ms 6892 KB Output is correct
118 Correct 11 ms 7164 KB Output is correct
119 Correct 11 ms 6928 KB Output is correct
120 Correct 11 ms 7116 KB Output is correct
121 Correct 217 ms 7156 KB Output is correct
122 Correct 196 ms 7116 KB Output is correct
123 Correct 96 ms 7040 KB Output is correct
124 Correct 11 ms 7116 KB Output is correct
125 Correct 11 ms 6860 KB Output is correct
126 Correct 34 ms 6788 KB Output is correct
127 Correct 309 ms 7296 KB Output is correct

Subtask #3
12.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6092 KB Output is correct
2 Correct 10 ms 6220 KB Output is correct
3 Correct 9 ms 6220 KB Output is correct
4 Correct 9 ms 6208 KB Output is correct
5 Correct 7 ms 6256 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 8 ms 6220 KB Output is correct
8 Correct 8 ms 6184 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 9 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 8 ms 6120 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6272 KB Output is correct
15 Correct 8 ms 6272 KB Output is correct
16 Correct 9 ms 6220 KB Output is correct
17 Correct 8 ms 6204 KB Output is correct
18 Correct 9 ms 6168 KB Output is correct
19 Correct 8 ms 6220 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6220 KB Output is correct
22 Correct 8 ms 6212 KB Output is correct
23 Correct 8 ms 6220 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 7 ms 6220 KB Output is correct
26 Correct 8 ms 6220 KB Output is correct
27 Correct 8 ms 6220 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6248 KB Output is correct
30 Correct 7 ms 6220 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct
32 Correct 8 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6220 KB Output is correct
35 Correct 10 ms 6276 KB Output is correct
36 Correct 9 ms 6220 KB Output is correct
37 Correct 10 ms 6224 KB Output is correct
38 Correct 8 ms 6212 KB Output is correct
39 Correct 9 ms 6220 KB Output is correct
40 Correct 9 ms 6264 KB Output is correct
41 Correct 8 ms 6248 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 8 ms 6220 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 9 ms 6180 KB Output is correct
46 Correct 8 ms 6220 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6220 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6220 KB Output is correct
51 Correct 8 ms 6244 KB Output is correct
52 Correct 10 ms 6220 KB Output is correct
53 Correct 8 ms 6220 KB Output is correct
54 Correct 8 ms 6220 KB Output is correct
55 Correct 9 ms 6220 KB Output is correct
56 Correct 8 ms 6220 KB Output is correct
57 Correct 8 ms 6268 KB Output is correct
58 Correct 8 ms 6236 KB Output is correct
59 Correct 8 ms 6220 KB Output is correct
60 Correct 11 ms 6604 KB Output is correct
61 Correct 10 ms 6424 KB Output is correct
62 Correct 9 ms 6580 KB Output is correct
63 Correct 11 ms 6988 KB Output is correct
64 Correct 11 ms 7372 KB Output is correct
65 Correct 12 ms 6860 KB Output is correct
66 Correct 11 ms 6860 KB Output is correct
67 Correct 50 ms 7396 KB Output is correct
68 Correct 9 ms 6604 KB Output is correct
69 Correct 11 ms 6348 KB Output is correct
70 Correct 11 ms 6656 KB Output is correct
71 Correct 10 ms 6596 KB Output is correct
72 Correct 10 ms 6600 KB Output is correct
73 Correct 66 ms 6604 KB Output is correct
74 Correct 260 ms 7072 KB Output is correct
75 Correct 99 ms 6860 KB Output is correct
76 Correct 14 ms 6988 KB Output is correct
77 Correct 11 ms 6476 KB Output is correct
78 Correct 22 ms 6488 KB Output is correct
79 Correct 12 ms 6476 KB Output is correct
80 Correct 171 ms 6824 KB Output is correct
81 Correct 199 ms 6916 KB Output is correct
82 Correct 91 ms 6724 KB Output is correct
83 Correct 106 ms 7048 KB Output is correct
84 Correct 11 ms 6732 KB Output is correct
85 Correct 261 ms 7096 KB Output is correct
86 Correct 13 ms 6860 KB Output is correct
87 Correct 12 ms 7148 KB Output is correct
88 Correct 12 ms 7112 KB Output is correct
89 Correct 11 ms 6988 KB Output is correct
90 Correct 40 ms 6628 KB Output is correct
91 Correct 81 ms 7056 KB Output is correct
92 Correct 239 ms 7272 KB Output is correct
93 Correct 24 ms 7056 KB Output is correct
94 Correct 12 ms 6860 KB Output is correct
95 Correct 22 ms 6776 KB Output is correct
96 Correct 12 ms 6604 KB Output is correct
97 Correct 68 ms 6604 KB Output is correct
98 Correct 81 ms 6696 KB Output is correct
99 Correct 69 ms 6604 KB Output is correct
100 Correct 199 ms 6980 KB Output is correct
101 Correct 37 ms 6944 KB Output is correct
102 Correct 77 ms 7004 KB Output is correct
103 Correct 14 ms 6988 KB Output is correct
104 Correct 11 ms 7016 KB Output is correct
105 Correct 14 ms 7064 KB Output is correct
106 Correct 12 ms 6828 KB Output is correct
107 Correct 12 ms 7252 KB Output is correct
108 Correct 12 ms 6940 KB Output is correct
109 Correct 13 ms 6912 KB Output is correct
110 Correct 16 ms 7128 KB Output is correct
111 Correct 11 ms 6988 KB Output is correct
112 Correct 11 ms 7180 KB Output is correct
113 Correct 11 ms 6988 KB Output is correct
114 Correct 11 ms 7080 KB Output is correct
115 Correct 10 ms 6860 KB Output is correct
116 Correct 11 ms 7204 KB Output is correct
117 Correct 11 ms 6892 KB Output is correct
118 Correct 11 ms 7164 KB Output is correct
119 Correct 11 ms 6928 KB Output is correct
120 Correct 11 ms 7116 KB Output is correct
121 Correct 217 ms 7156 KB Output is correct
122 Correct 196 ms 7116 KB Output is correct
123 Correct 96 ms 7040 KB Output is correct
124 Correct 11 ms 7116 KB Output is correct
125 Correct 11 ms 6860 KB Output is correct
126 Correct 34 ms 6788 KB Output is correct
127 Correct 309 ms 7296 KB Output is correct
128 Correct 8 ms 6220 KB Output is correct
129 Correct 145 ms 20040 KB Output is correct
130 Correct 183 ms 29204 KB Output is correct
131 Correct 129 ms 31760 KB Output is correct
132 Correct 106 ms 18600 KB Output is correct
133 Partially correct 130 ms 21112 KB Output is partially correct
134 Partially correct 128 ms 21060 KB Output is partially correct
135 Correct 131 ms 18404 KB Output is correct
136 Correct 133 ms 22420 KB Output is correct
137 Partially correct 100 ms 19644 KB Output is partially correct
138 Partially correct 150 ms 27744 KB Output is partially correct
139 Correct 334 ms 41352 KB Output is correct
140 Partially correct 444 ms 46480 KB Output is partially correct
141 Correct 388 ms 36956 KB Output is correct
142 Correct 552 ms 50176 KB Output is correct
143 Correct 528 ms 49004 KB Output is correct
144 Correct 490 ms 44940 KB Output is correct
145 Partially correct 453 ms 58108 KB Output is partially correct
146 Partially correct 317 ms 39580 KB Output is partially correct
147 Partially correct 386 ms 54708 KB Output is partially correct
148 Correct 712 ms 36644 KB Output is correct
149 Partially correct 112 ms 17756 KB Output is partially correct
150 Correct 142 ms 20168 KB Output is correct
151 Correct 163 ms 24296 KB Output is correct
152 Correct 138 ms 19584 KB Output is correct
153 Correct 144 ms 19144 KB Output is correct
154 Correct 164 ms 18628 KB Output is correct
155 Correct 137 ms 23328 KB Output is correct
156 Partially correct 101 ms 21264 KB Output is partially correct
157 Correct 119 ms 18048 KB Output is correct
158 Partially correct 99 ms 19660 KB Output is partially correct
159 Partially correct 94 ms 25156 KB Output is partially correct
160 Partially correct 326 ms 33452 KB Output is partially correct
161 Partially correct 361 ms 46484 KB Output is partially correct
162 Correct 590 ms 63484 KB Output is correct
163 Correct 502 ms 55236 KB Output is correct
164 Partially correct 447 ms 53960 KB Output is partially correct
165 Partially correct 533 ms 39108 KB Output is partially correct
166 Partially correct 383 ms 38984 KB Output is partially correct
167 Correct 645 ms 57572 KB Output is correct
168 Partially correct 316 ms 41572 KB Output is partially correct
169 Partially correct 293 ms 42824 KB Output is partially correct
170 Partially correct 299 ms 37012 KB Output is partially correct
171 Correct 440 ms 28948 KB Output is correct
172 Correct 570 ms 39160 KB Output is correct
173 Correct 466 ms 48532 KB Output is correct
174 Correct 436 ms 50000 KB Output is correct
175 Correct 428 ms 45404 KB Output is correct
176 Correct 454 ms 44596 KB Output is correct
177 Correct 424 ms 44580 KB Output is correct
178 Correct 522 ms 62404 KB Output is correct
179 Partially correct 291 ms 42812 KB Output is partially correct
180 Partially correct 305 ms 42872 KB Output is partially correct
181 Partially correct 277 ms 27716 KB Output is partially correct
182 Correct 455 ms 44008 KB Output is correct
183 Correct 441 ms 53236 KB Output is correct
184 Partially correct 362 ms 35960 KB Output is partially correct
185 Partially correct 374 ms 33892 KB Output is partially correct
186 Partially correct 302 ms 31300 KB Output is partially correct

Subtask #4
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6092 KB Output is correct
2 Correct 10 ms 6220 KB Output is correct
3 Correct 9 ms 6220 KB Output is correct
4 Correct 9 ms 6208 KB Output is correct
5 Correct 7 ms 6256 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 8 ms 6220 KB Output is correct
8 Correct 8 ms 6184 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 9 ms 6220 KB Output is correct
11 Correct 8 ms 6220 KB Output is correct
12 Correct 8 ms 6120 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6272 KB Output is correct
15 Correct 8 ms 6272 KB Output is correct
16 Correct 9 ms 6220 KB Output is correct
17 Correct 8 ms 6204 KB Output is correct
18 Correct 9 ms 6168 KB Output is correct
19 Correct 8 ms 6220 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6220 KB Output is correct
22 Correct 8 ms 6212 KB Output is correct
23 Correct 8 ms 6220 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 7 ms 6220 KB Output is correct
26 Correct 8 ms 6220 KB Output is correct
27 Correct 8 ms 6220 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6248 KB Output is correct
30 Correct 7 ms 6220 KB Output is correct
31 Correct 8 ms 6220 KB Output is correct
32 Correct 8 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6220 KB Output is correct
35 Correct 10 ms 6276 KB Output is correct
36 Correct 9 ms 6220 KB Output is correct
37 Correct 10 ms 6224 KB Output is correct
38 Correct 8 ms 6212 KB Output is correct
39 Correct 9 ms 6220 KB Output is correct
40 Correct 9 ms 6264 KB Output is correct
41 Correct 8 ms 6248 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 8 ms 6220 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 9 ms 6180 KB Output is correct
46 Correct 8 ms 6220 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6220 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6220 KB Output is correct
51 Correct 8 ms 6244 KB Output is correct
52 Correct 10 ms 6220 KB Output is correct
53 Correct 8 ms 6220 KB Output is correct
54 Correct 8 ms 6220 KB Output is correct
55 Correct 9 ms 6220 KB Output is correct
56 Correct 8 ms 6220 KB Output is correct
57 Correct 8 ms 6268 KB Output is correct
58 Correct 8 ms 6236 KB Output is correct
59 Correct 8 ms 6220 KB Output is correct
60 Correct 11 ms 6604 KB Output is correct
61 Correct 10 ms 6424 KB Output is correct
62 Correct 9 ms 6580 KB Output is correct
63 Correct 11 ms 6988 KB Output is correct
64 Correct 11 ms 7372 KB Output is correct
65 Correct 12 ms 6860 KB Output is correct
66 Correct 11 ms 6860 KB Output is correct
67 Correct 50 ms 7396 KB Output is correct
68 Correct 9 ms 6604 KB Output is correct
69 Correct 11 ms 6348 KB Output is correct
70 Correct 11 ms 6656 KB Output is correct
71 Correct 10 ms 6596 KB Output is correct
72 Correct 10 ms 6600 KB Output is correct
73 Correct 66 ms 6604 KB Output is correct
74 Correct 260 ms 7072 KB Output is correct
75 Correct 99 ms 6860 KB Output is correct
76 Correct 14 ms 6988 KB Output is correct
77 Correct 11 ms 6476 KB Output is correct
78 Correct 22 ms 6488 KB Output is correct
79 Correct 12 ms 6476 KB Output is correct
80 Correct 171 ms 6824 KB Output is correct
81 Correct 199 ms 6916 KB Output is correct
82 Correct 91 ms 6724 KB Output is correct
83 Correct 106 ms 7048 KB Output is correct
84 Correct 11 ms 6732 KB Output is correct
85 Correct 261 ms 7096 KB Output is correct
86 Correct 13 ms 6860 KB Output is correct
87 Correct 12 ms 7148 KB Output is correct
88 Correct 12 ms 7112 KB Output is correct
89 Correct 11 ms 6988 KB Output is correct
90 Correct 40 ms 6628 KB Output is correct
91 Correct 81 ms 7056 KB Output is correct
92 Correct 239 ms 7272 KB Output is correct
93 Correct 24 ms 7056 KB Output is correct
94 Correct 12 ms 6860 KB Output is correct
95 Correct 22 ms 6776 KB Output is correct
96 Correct 12 ms 6604 KB Output is correct
97 Correct 68 ms 6604 KB Output is correct
98 Correct 81 ms 6696 KB Output is correct
99 Correct 69 ms 6604 KB Output is correct
100 Correct 199 ms 6980 KB Output is correct
101 Correct 37 ms 6944 KB Output is correct
102 Correct 77 ms 7004 KB Output is correct
103 Correct 14 ms 6988 KB Output is correct
104 Correct 11 ms 7016 KB Output is correct
105 Correct 14 ms 7064 KB Output is correct
106 Correct 12 ms 6828 KB Output is correct
107 Correct 12 ms 7252 KB Output is correct
108 Correct 12 ms 6940 KB Output is correct
109 Correct 13 ms 6912 KB Output is correct
110 Correct 16 ms 7128 KB Output is correct
111 Correct 11 ms 6988 KB Output is correct
112 Correct 11 ms 7180 KB Output is correct
113 Correct 11 ms 6988 KB Output is correct
114 Correct 11 ms 7080 KB Output is correct
115 Correct 10 ms 6860 KB Output is correct
116 Correct 11 ms 7204 KB Output is correct
117 Correct 11 ms 6892 KB Output is correct
118 Correct 11 ms 7164 KB Output is correct
119 Correct 11 ms 6928 KB Output is correct
120 Correct 11 ms 7116 KB Output is correct
121 Correct 217 ms 7156 KB Output is correct
122 Correct 196 ms 7116 KB Output is correct
123 Correct 96 ms 7040 KB Output is correct
124 Correct 11 ms 7116 KB Output is correct
125 Correct 11 ms 6860 KB Output is correct
126 Correct 34 ms 6788 KB Output is correct
127 Correct 309 ms 7296 KB Output is correct
128 Correct 8 ms 6220 KB Output is correct
129 Correct 145 ms 20040 KB Output is correct
130 Correct 183 ms 29204 KB Output is correct
131 Correct 129 ms 31760 KB Output is correct
132 Correct 106 ms 18600 KB Output is correct
133 Partially correct 130 ms 21112 KB Output is partially correct
134 Partially correct 128 ms 21060 KB Output is partially correct
135 Correct 131 ms 18404 KB Output is correct
136 Correct 133 ms 22420 KB Output is correct
137 Partially correct 100 ms 19644 KB Output is partially correct
138 Partially correct 150 ms 27744 KB Output is partially correct
139 Correct 334 ms 41352 KB Output is correct
140 Partially correct 444 ms 46480 KB Output is partially correct
141 Correct 388 ms 36956 KB Output is correct
142 Correct 552 ms 50176 KB Output is correct
143 Correct 528 ms 49004 KB Output is correct
144 Correct 490 ms 44940 KB Output is correct
145 Partially correct 453 ms 58108 KB Output is partially correct
146 Partially correct 317 ms 39580 KB Output is partially correct
147 Partially correct 386 ms 54708 KB Output is partially correct
148 Correct 712 ms 36644 KB Output is correct
149 Partially correct 112 ms 17756 KB Output is partially correct
150 Correct 142 ms 20168 KB Output is correct
151 Correct 163 ms 24296 KB Output is correct
152 Correct 138 ms 19584 KB Output is correct
153 Correct 144 ms 19144 KB Output is correct
154 Correct 164 ms 18628 KB Output is correct
155 Correct 137 ms 23328 KB Output is correct
156 Partially correct 101 ms 21264 KB Output is partially correct
157 Correct 119 ms 18048 KB Output is correct
158 Partially correct 99 ms 19660 KB Output is partially correct
159 Partially correct 94 ms 25156 KB Output is partially correct
160 Partially correct 326 ms 33452 KB Output is partially correct
161 Partially correct 361 ms 46484 KB Output is partially correct
162 Correct 590 ms 63484 KB Output is correct
163 Correct 502 ms 55236 KB Output is correct
164 Partially correct 447 ms 53960 KB Output is partially correct
165 Partially correct 533 ms 39108 KB Output is partially correct
166 Partially correct 383 ms 38984 KB Output is partially correct
167 Correct 645 ms 57572 KB Output is correct
168 Partially correct 316 ms 41572 KB Output is partially correct
169 Partially correct 293 ms 42824 KB Output is partially correct
170 Partially correct 299 ms 37012 KB Output is partially correct
171 Correct 440 ms 28948 KB Output is correct
172 Correct 570 ms 39160 KB Output is correct
173 Correct 466 ms 48532 KB Output is correct
174 Correct 436 ms 50000 KB Output is correct
175 Correct 428 ms 45404 KB Output is correct
176 Correct 454 ms 44596 KB Output is correct
177 Correct 424 ms 44580 KB Output is correct
178 Correct 522 ms 62404 KB Output is correct
179 Partially correct 291 ms 42812 KB Output is partially correct
180 Partially correct 305 ms 42872 KB Output is partially correct
181 Partially correct 277 ms 27716 KB Output is partially correct
182 Correct 455 ms 44008 KB Output is correct
183 Correct 441 ms 53236 KB Output is correct
184 Partially correct 362 ms 35960 KB Output is partially correct
185 Partially correct 374 ms 33892 KB Output is partially correct
186 Partially correct 302 ms 31300 KB Output is partially correct
187 Correct 1793 ms 132536 KB Output is correct
188 Partially correct 1495 ms 113748 KB Output is partially correct
189 Partially correct 1739 ms 135320 KB Output is partially correct
190 Partially correct 1436 ms 113636 KB Output is partially correct
191 Partially correct 1351 ms 113332 KB Output is partially correct
192 Partially correct 1350 ms 113772 KB Output is partially correct
193 Partially correct 1548 ms 128460 KB Output is partially correct
194 Correct 1569 ms 129156 KB Output is correct
195 Partially correct 1534 ms 109976 KB Output is partially correct
196 Partially correct 1490 ms 94072 KB Output is partially correct
197 Partially correct 1440 ms 93060 KB Output is partially correct
198 Partially correct 1447 ms 99028 KB Output is partially correct
199 Correct 1557 ms 93212 KB Output is correct
200 Partially correct 1487 ms 98396 KB Output is partially correct
201 Partially correct 1604 ms 92664 KB Output is partially correct
202 Correct 1934 ms 97060 KB Output is correct
203 Correct 1342 ms 103912 KB Output is correct
204 Correct 2517 ms 120724 KB Output is correct
205 Correct 2836 ms 120260 KB Output is correct
206 Correct 1893 ms 120524 KB Output is correct
207 Correct 2368 ms 120268 KB Output is correct
208 Correct 1483 ms 93216 KB Output is correct
209 Correct 2661 ms 148672 KB Output is correct
210 Partially correct 1414 ms 105412 KB Output is partially correct
211 Partially correct 1788 ms 118048 KB Output is partially correct
212 Correct 1958 ms 124444 KB Output is correct
213 Partially correct 1394 ms 105624 KB Output is partially correct
214 Partially correct 1621 ms 195196 KB Output is partially correct
215 Partially correct 1682 ms 193344 KB Output is partially correct
216 Correct 2246 ms 218136 KB Output is correct
217 Correct 1849 ms 95740 KB Output is correct
218 Correct 2265 ms 117724 KB Output is correct
219 Correct 1511 ms 129544 KB Output is correct
220 Partially correct 1598 ms 135236 KB Output is partially correct
221 Correct 1489 ms 101696 KB Output is correct
222 Partially correct 1477 ms 102472 KB Output is partially correct
223 Correct 2246 ms 181248 KB Output is correct
224 Correct 2354 ms 149820 KB Output is correct
225 Partially correct 1541 ms 129088 KB Output is partially correct
226 Partially correct 1786 ms 219380 KB Output is partially correct
227 Correct 2946 ms 116884 KB Output is correct
228 Correct 1985 ms 116236 KB Output is correct
229 Correct 1916 ms 144368 KB Output is correct
230 Partially correct 1527 ms 108956 KB Output is partially correct
231 Partially correct 1454 ms 100180 KB Output is partially correct
232 Partially correct 1539 ms 131244 KB Output is partially correct
233 Correct 2212 ms 193316 KB Output is correct
234 Correct 1630 ms 109220 KB Output is correct
235 Correct 1980 ms 169244 KB Output is correct
236 Correct 1767 ms 116776 KB Output is correct
237 Partially correct 1400 ms 96528 KB Output is partially correct
238 Correct 1809 ms 135536 KB Output is correct
239 Correct 1682 ms 121088 KB Output is correct
240 Correct 1625 ms 129880 KB Output is correct
241 Correct 1970 ms 161400 KB Output is correct
242 Correct 1812 ms 143592 KB Output is correct