oj.uz

Submission #504048

# Submission time Handle Problem Language Result Execution time Memory
504048 2022-01-09T15:09:51 Z rainboy Wells (CEOI21_wells) C
80 / 100
 2969 ms 213848 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]; int xx[N];

void mark_bad_and_count() {
	static int aa[N + 1];
	static int yy[N], zz[N];
	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;
			}
		}
	for (r = 0; r < k; r++)
		yy[r] = zz[r] = 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 + d + hh[i] >= k - 1) {
				if (g + 1 < k)
					yy[g + 1] = (long long) yy[g + 1] * dfs3(pp[i], i, k - 1 - (g + d)) % MD;
			} else {
				if (g > l - k)
					zz[g - 1 - l + k] = (long long) zz[g - 1 - l + k] * dfs3(pp[i], i, k - 1 - (l - 1 - g + d)) % MD;
			}
		}
	for (r = 1; r < k; r++)
		yy[r] = (long long) yy[r] * yy[r - 1] % MD;
	for (r = k - 2; r >= 0; r--)
		zz[r] = (long long) zz[r] * zz[r + 1] % MD;
	for (r = 0; r < k; r++)
		xx[r] = (long long) yy[r] * zz[(r - l % k + k) % k] % MD;
}

int yes, ans;

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

	if (bad[r])
		return;
	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 >= r ? ((g + d) % k == r ? 1 : 0) : ((g - d % k + k) % k == r ? 1 : 0);
	}
	for (g = 0; g < l; g++)
		if (type[ii[g]] == 1 && !dfs4(-1, ii[g]))
			return;
	yes = 1, ans = (ans + xx[r]) % 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_and_count();
	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:192:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  192 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
wells.c:199:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
  199 |   scanf("%d%d", &i, &j), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6152 KB Output is correct
2 Correct 8 ms 6292 KB Output is correct
3 Correct 8 ms 6204 KB Output is correct
4 Correct 8 ms 6220 KB Output is correct
5 Correct 9 ms 6284 KB Output is correct
6 Correct 8 ms 6200 KB Output is correct
7 Correct 8 ms 6288 KB Output is correct
8 Correct 10 ms 6288 KB Output is correct
9 Correct 8 ms 6212 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 9 ms 6220 KB Output is correct
12 Correct 8 ms 6168 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6288 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6200 KB Output is correct
17 Correct 8 ms 6220 KB Output is correct
18 Correct 8 ms 6220 KB Output is correct
19 Correct 8 ms 6288 KB Output is correct
20 Correct 8 ms 6176 KB Output is correct
21 Correct 8 ms 6228 KB Output is correct
22 Correct 8 ms 6292 KB Output is correct
23 Correct 9 ms 6212 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6288 KB Output is correct
26 Correct 8 ms 6284 KB Output is correct
27 Correct 8 ms 6320 KB Output is correct
28 Correct 9 ms 6220 KB Output is correct
29 Correct 8 ms 6256 KB Output is correct
30 Correct 9 ms 6276 KB Output is correct
31 Correct 8 ms 6292 KB Output is correct
32 Correct 8 ms 6236 KB Output is correct
33 Correct 8 ms 6296 KB Output is correct
34 Correct 8 ms 6252 KB Output is correct
35 Correct 9 ms 6220 KB Output is correct
36 Correct 9 ms 6380 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 9 ms 6232 KB Output is correct
39 Correct 9 ms 6300 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6220 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 9 ms 6300 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 8 ms 6220 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 6212 KB Output is correct
49 Correct 8 ms 6284 KB Output is correct
50 Correct 8 ms 6284 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 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 8 ms 6220 KB Output is correct
56 Correct 9 ms 6220 KB Output is correct
57 Correct 8 ms 6220 KB Output is correct
58 Correct 8 ms 6164 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6152 KB Output is correct
2 Correct 8 ms 6292 KB Output is correct
3 Correct 8 ms 6204 KB Output is correct
4 Correct 8 ms 6220 KB Output is correct
5 Correct 9 ms 6284 KB Output is correct
6 Correct 8 ms 6200 KB Output is correct
7 Correct 8 ms 6288 KB Output is correct
8 Correct 10 ms 6288 KB Output is correct
9 Correct 8 ms 6212 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 9 ms 6220 KB Output is correct
12 Correct 8 ms 6168 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6288 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6200 KB Output is correct
17 Correct 8 ms 6220 KB Output is correct
18 Correct 8 ms 6220 KB Output is correct
19 Correct 8 ms 6288 KB Output is correct
20 Correct 8 ms 6176 KB Output is correct
21 Correct 8 ms 6228 KB Output is correct
22 Correct 8 ms 6292 KB Output is correct
23 Correct 9 ms 6212 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6288 KB Output is correct
26 Correct 8 ms 6284 KB Output is correct
27 Correct 8 ms 6320 KB Output is correct
28 Correct 9 ms 6220 KB Output is correct
29 Correct 8 ms 6256 KB Output is correct
30 Correct 9 ms 6276 KB Output is correct
31 Correct 8 ms 6292 KB Output is correct
32 Correct 8 ms 6236 KB Output is correct
33 Correct 8 ms 6296 KB Output is correct
34 Correct 8 ms 6252 KB Output is correct
35 Correct 9 ms 6220 KB Output is correct
36 Correct 9 ms 6380 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 9 ms 6232 KB Output is correct
39 Correct 9 ms 6300 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6220 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 9 ms 6300 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 8 ms 6220 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 6212 KB Output is correct
49 Correct 8 ms 6284 KB Output is correct
50 Correct 8 ms 6284 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 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 8 ms 6220 KB Output is correct
56 Correct 9 ms 6220 KB Output is correct
57 Correct 8 ms 6220 KB Output is correct
58 Correct 8 ms 6164 KB Output is correct
59 Correct 8 ms 6240 KB Output is correct
60 Correct 10 ms 6604 KB Output is correct
61 Correct 9 ms 6476 KB Output is correct
62 Correct 9 ms 6648 KB Output is correct
63 Correct 11 ms 7064 KB Output is correct
64 Correct 12 ms 7512 KB Output is correct
65 Correct 12 ms 6944 KB Output is correct
66 Correct 11 ms 6988 KB Output is correct
67 Correct 34 ms 7500 KB Output is correct
68 Correct 10 ms 6604 KB Output is correct
69 Correct 9 ms 6436 KB Output is correct
70 Correct 11 ms 6728 KB Output is correct
71 Correct 9 ms 6604 KB Output is correct
72 Correct 10 ms 6620 KB Output is correct
73 Correct 34 ms 6748 KB Output is correct
74 Correct 118 ms 7180 KB Output is correct
75 Correct 28 ms 6944 KB Output is correct
76 Correct 12 ms 7104 KB Output is correct
77 Correct 10 ms 6476 KB Output is correct
78 Correct 12 ms 6604 KB Output is correct
79 Correct 10 ms 6532 KB Output is correct
80 Correct 76 ms 7028 KB Output is correct
81 Correct 81 ms 7044 KB Output is correct
82 Correct 29 ms 6944 KB Output is correct
83 Correct 49 ms 7116 KB Output is correct
84 Correct 11 ms 6880 KB Output is correct
85 Correct 103 ms 7220 KB Output is correct
86 Correct 12 ms 6944 KB Output is correct
87 Correct 13 ms 7236 KB Output is correct
88 Correct 11 ms 7136 KB Output is correct
89 Correct 12 ms 7112 KB Output is correct
90 Correct 36 ms 6688 KB Output is correct
91 Correct 42 ms 7160 KB Output is correct
92 Correct 127 ms 7316 KB Output is correct
93 Correct 20 ms 7244 KB Output is correct
94 Correct 11 ms 6964 KB Output is correct
95 Correct 14 ms 6896 KB Output is correct
96 Correct 11 ms 6668 KB Output is correct
97 Correct 38 ms 6688 KB Output is correct
98 Correct 38 ms 6772 KB Output is correct
99 Correct 23 ms 6784 KB Output is correct
100 Correct 57 ms 7108 KB Output is correct
101 Correct 21 ms 6988 KB Output is correct
102 Correct 48 ms 7116 KB Output is correct
103 Correct 11 ms 7096 KB Output is correct
104 Correct 11 ms 7116 KB Output is correct
105 Correct 12 ms 7256 KB Output is correct
106 Correct 12 ms 6872 KB Output is correct
107 Correct 13 ms 7340 KB Output is correct
108 Correct 11 ms 6988 KB Output is correct
109 Correct 12 ms 6988 KB Output is correct
110 Correct 16 ms 7116 KB Output is correct
111 Correct 12 ms 7064 KB Output is correct
112 Correct 11 ms 7320 KB Output is correct
113 Correct 11 ms 7108 KB Output is correct
114 Correct 11 ms 7204 KB Output is correct
115 Correct 11 ms 6988 KB Output is correct
116 Correct 11 ms 7328 KB Output is correct
117 Correct 11 ms 7008 KB Output is correct
118 Correct 11 ms 7328 KB Output is correct
119 Correct 11 ms 7024 KB Output is correct
120 Correct 13 ms 7360 KB Output is correct
121 Correct 179 ms 7268 KB Output is correct
122 Correct 173 ms 7268 KB Output is correct
123 Correct 74 ms 7096 KB Output is correct
124 Correct 11 ms 7244 KB Output is correct
125 Correct 11 ms 6940 KB Output is correct
126 Correct 16 ms 6820 KB Output is correct
127 Correct 250 ms 7492 KB Output is correct

Subtask #3
12.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6152 KB Output is correct
2 Correct 8 ms 6292 KB Output is correct
3 Correct 8 ms 6204 KB Output is correct
4 Correct 8 ms 6220 KB Output is correct
5 Correct 9 ms 6284 KB Output is correct
6 Correct 8 ms 6200 KB Output is correct
7 Correct 8 ms 6288 KB Output is correct
8 Correct 10 ms 6288 KB Output is correct
9 Correct 8 ms 6212 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 9 ms 6220 KB Output is correct
12 Correct 8 ms 6168 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6288 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6200 KB Output is correct
17 Correct 8 ms 6220 KB Output is correct
18 Correct 8 ms 6220 KB Output is correct
19 Correct 8 ms 6288 KB Output is correct
20 Correct 8 ms 6176 KB Output is correct
21 Correct 8 ms 6228 KB Output is correct
22 Correct 8 ms 6292 KB Output is correct
23 Correct 9 ms 6212 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6288 KB Output is correct
26 Correct 8 ms 6284 KB Output is correct
27 Correct 8 ms 6320 KB Output is correct
28 Correct 9 ms 6220 KB Output is correct
29 Correct 8 ms 6256 KB Output is correct
30 Correct 9 ms 6276 KB Output is correct
31 Correct 8 ms 6292 KB Output is correct
32 Correct 8 ms 6236 KB Output is correct
33 Correct 8 ms 6296 KB Output is correct
34 Correct 8 ms 6252 KB Output is correct
35 Correct 9 ms 6220 KB Output is correct
36 Correct 9 ms 6380 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 9 ms 6232 KB Output is correct
39 Correct 9 ms 6300 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6220 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 9 ms 6300 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 8 ms 6220 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 6212 KB Output is correct
49 Correct 8 ms 6284 KB Output is correct
50 Correct 8 ms 6284 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 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 8 ms 6220 KB Output is correct
56 Correct 9 ms 6220 KB Output is correct
57 Correct 8 ms 6220 KB Output is correct
58 Correct 8 ms 6164 KB Output is correct
59 Correct 8 ms 6240 KB Output is correct
60 Correct 10 ms 6604 KB Output is correct
61 Correct 9 ms 6476 KB Output is correct
62 Correct 9 ms 6648 KB Output is correct
63 Correct 11 ms 7064 KB Output is correct
64 Correct 12 ms 7512 KB Output is correct
65 Correct 12 ms 6944 KB Output is correct
66 Correct 11 ms 6988 KB Output is correct
67 Correct 34 ms 7500 KB Output is correct
68 Correct 10 ms 6604 KB Output is correct
69 Correct 9 ms 6436 KB Output is correct
70 Correct 11 ms 6728 KB Output is correct
71 Correct 9 ms 6604 KB Output is correct
72 Correct 10 ms 6620 KB Output is correct
73 Correct 34 ms 6748 KB Output is correct
74 Correct 118 ms 7180 KB Output is correct
75 Correct 28 ms 6944 KB Output is correct
76 Correct 12 ms 7104 KB Output is correct
77 Correct 10 ms 6476 KB Output is correct
78 Correct 12 ms 6604 KB Output is correct
79 Correct 10 ms 6532 KB Output is correct
80 Correct 76 ms 7028 KB Output is correct
81 Correct 81 ms 7044 KB Output is correct
82 Correct 29 ms 6944 KB Output is correct
83 Correct 49 ms 7116 KB Output is correct
84 Correct 11 ms 6880 KB Output is correct
85 Correct 103 ms 7220 KB Output is correct
86 Correct 12 ms 6944 KB Output is correct
87 Correct 13 ms 7236 KB Output is correct
88 Correct 11 ms 7136 KB Output is correct
89 Correct 12 ms 7112 KB Output is correct
90 Correct 36 ms 6688 KB Output is correct
91 Correct 42 ms 7160 KB Output is correct
92 Correct 127 ms 7316 KB Output is correct
93 Correct 20 ms 7244 KB Output is correct
94 Correct 11 ms 6964 KB Output is correct
95 Correct 14 ms 6896 KB Output is correct
96 Correct 11 ms 6668 KB Output is correct
97 Correct 38 ms 6688 KB Output is correct
98 Correct 38 ms 6772 KB Output is correct
99 Correct 23 ms 6784 KB Output is correct
100 Correct 57 ms 7108 KB Output is correct
101 Correct 21 ms 6988 KB Output is correct
102 Correct 48 ms 7116 KB Output is correct
103 Correct 11 ms 7096 KB Output is correct
104 Correct 11 ms 7116 KB Output is correct
105 Correct 12 ms 7256 KB Output is correct
106 Correct 12 ms 6872 KB Output is correct
107 Correct 13 ms 7340 KB Output is correct
108 Correct 11 ms 6988 KB Output is correct
109 Correct 12 ms 6988 KB Output is correct
110 Correct 16 ms 7116 KB Output is correct
111 Correct 12 ms 7064 KB Output is correct
112 Correct 11 ms 7320 KB Output is correct
113 Correct 11 ms 7108 KB Output is correct
114 Correct 11 ms 7204 KB Output is correct
115 Correct 11 ms 6988 KB Output is correct
116 Correct 11 ms 7328 KB Output is correct
117 Correct 11 ms 7008 KB Output is correct
118 Correct 11 ms 7328 KB Output is correct
119 Correct 11 ms 7024 KB Output is correct
120 Correct 13 ms 7360 KB Output is correct
121 Correct 179 ms 7268 KB Output is correct
122 Correct 173 ms 7268 KB Output is correct
123 Correct 74 ms 7096 KB Output is correct
124 Correct 11 ms 7244 KB Output is correct
125 Correct 11 ms 6940 KB Output is correct
126 Correct 16 ms 6820 KB Output is correct
127 Correct 250 ms 7492 KB Output is correct
128 Correct 9 ms 6168 KB Output is correct
129 Correct 123 ms 21256 KB Output is correct
130 Correct 129 ms 30736 KB Output is correct
131 Correct 135 ms 33608 KB Output is correct
132 Correct 98 ms 19716 KB Output is correct
133 Partially correct 103 ms 22632 KB Output is partially correct
134 Partially correct 104 ms 22812 KB Output is partially correct
135 Correct 124 ms 19656 KB Output is correct
136 Correct 134 ms 23640 KB Output is correct
137 Partially correct 95 ms 21036 KB Output is partially correct
138 Partially correct 103 ms 29464 KB Output is partially correct
139 Correct 361 ms 42668 KB Output is correct
140 Partially correct 345 ms 48708 KB Output is partially correct
141 Correct 381 ms 38204 KB Output is correct
142 Correct 524 ms 51908 KB Output is correct
143 Correct 486 ms 50512 KB Output is correct
144 Correct 468 ms 46148 KB Output is correct
145 Partially correct 430 ms 61068 KB Output is partially correct
146 Partially correct 297 ms 40732 KB Output is partially correct
147 Partially correct 369 ms 57044 KB Output is partially correct
148 Correct 684 ms 37908 KB Output is correct
149 Partially correct 102 ms 18912 KB Output is partially correct
150 Correct 134 ms 21508 KB Output is correct
151 Correct 125 ms 25580 KB Output is correct
152 Correct 122 ms 20812 KB Output is correct
153 Correct 138 ms 20416 KB Output is correct
154 Correct 149 ms 19780 KB Output is correct
155 Correct 132 ms 24736 KB Output is correct
156 Partially correct 96 ms 22636 KB Output is partially correct
157 Correct 92 ms 19220 KB Output is correct
158 Partially correct 96 ms 20968 KB Output is partially correct
159 Partially correct 94 ms 26764 KB Output is partially correct
160 Partially correct 280 ms 34984 KB Output is partially correct
161 Partially correct 362 ms 48812 KB Output is partially correct
162 Correct 567 ms 65908 KB Output is correct
163 Correct 493 ms 57164 KB Output is correct
164 Partially correct 444 ms 56644 KB Output is partially correct
165 Partially correct 449 ms 40904 KB Output is partially correct
166 Partially correct 391 ms 40912 KB Output is partially correct
167 Correct 613 ms 59628 KB Output is correct
168 Partially correct 306 ms 43756 KB Output is partially correct
169 Partially correct 293 ms 44692 KB Output is partially correct
170 Partially correct 271 ms 38588 KB Output is partially correct
171 Correct 431 ms 30228 KB Output is correct
172 Correct 571 ms 40192 KB Output is correct
173 Correct 489 ms 50756 KB Output is correct
174 Correct 444 ms 52040 KB Output is correct
175 Correct 419 ms 47172 KB Output is correct
176 Correct 409 ms 46240 KB Output is correct
177 Correct 406 ms 46464 KB Output is correct
178 Correct 556 ms 65408 KB Output is correct
179 Partially correct 349 ms 44688 KB Output is partially correct
180 Partially correct 329 ms 44996 KB Output is partially correct
181 Partially correct 344 ms 29528 KB Output is partially correct
182 Correct 514 ms 46624 KB Output is correct
183 Correct 527 ms 55736 KB Output is correct
184 Partially correct 431 ms 37624 KB Output is partially correct
185 Partially correct 435 ms 35348 KB Output is partially correct
186 Partially correct 363 ms 32700 KB Output is partially correct

Subtask #4
18.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6152 KB Output is correct
2 Correct 8 ms 6292 KB Output is correct
3 Correct 8 ms 6204 KB Output is correct
4 Correct 8 ms 6220 KB Output is correct
5 Correct 9 ms 6284 KB Output is correct
6 Correct 8 ms 6200 KB Output is correct
7 Correct 8 ms 6288 KB Output is correct
8 Correct 10 ms 6288 KB Output is correct
9 Correct 8 ms 6212 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 9 ms 6220 KB Output is correct
12 Correct 8 ms 6168 KB Output is correct
13 Correct 8 ms 6220 KB Output is correct
14 Correct 8 ms 6288 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6200 KB Output is correct
17 Correct 8 ms 6220 KB Output is correct
18 Correct 8 ms 6220 KB Output is correct
19 Correct 8 ms 6288 KB Output is correct
20 Correct 8 ms 6176 KB Output is correct
21 Correct 8 ms 6228 KB Output is correct
22 Correct 8 ms 6292 KB Output is correct
23 Correct 9 ms 6212 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6288 KB Output is correct
26 Correct 8 ms 6284 KB Output is correct
27 Correct 8 ms 6320 KB Output is correct
28 Correct 9 ms 6220 KB Output is correct
29 Correct 8 ms 6256 KB Output is correct
30 Correct 9 ms 6276 KB Output is correct
31 Correct 8 ms 6292 KB Output is correct
32 Correct 8 ms 6236 KB Output is correct
33 Correct 8 ms 6296 KB Output is correct
34 Correct 8 ms 6252 KB Output is correct
35 Correct 9 ms 6220 KB Output is correct
36 Correct 9 ms 6380 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 9 ms 6232 KB Output is correct
39 Correct 9 ms 6300 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6220 KB Output is correct
42 Correct 8 ms 6220 KB Output is correct
43 Correct 9 ms 6300 KB Output is correct
44 Correct 8 ms 6220 KB Output is correct
45 Correct 8 ms 6220 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 6212 KB Output is correct
49 Correct 8 ms 6284 KB Output is correct
50 Correct 8 ms 6284 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 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 8 ms 6220 KB Output is correct
56 Correct 9 ms 6220 KB Output is correct
57 Correct 8 ms 6220 KB Output is correct
58 Correct 8 ms 6164 KB Output is correct
59 Correct 8 ms 6240 KB Output is correct
60 Correct 10 ms 6604 KB Output is correct
61 Correct 9 ms 6476 KB Output is correct
62 Correct 9 ms 6648 KB Output is correct
63 Correct 11 ms 7064 KB Output is correct
64 Correct 12 ms 7512 KB Output is correct
65 Correct 12 ms 6944 KB Output is correct
66 Correct 11 ms 6988 KB Output is correct
67 Correct 34 ms 7500 KB Output is correct
68 Correct 10 ms 6604 KB Output is correct
69 Correct 9 ms 6436 KB Output is correct
70 Correct 11 ms 6728 KB Output is correct
71 Correct 9 ms 6604 KB Output is correct
72 Correct 10 ms 6620 KB Output is correct
73 Correct 34 ms 6748 KB Output is correct
74 Correct 118 ms 7180 KB Output is correct
75 Correct 28 ms 6944 KB Output is correct
76 Correct 12 ms 7104 KB Output is correct
77 Correct 10 ms 6476 KB Output is correct
78 Correct 12 ms 6604 KB Output is correct
79 Correct 10 ms 6532 KB Output is correct
80 Correct 76 ms 7028 KB Output is correct
81 Correct 81 ms 7044 KB Output is correct
82 Correct 29 ms 6944 KB Output is correct
83 Correct 49 ms 7116 KB Output is correct
84 Correct 11 ms 6880 KB Output is correct
85 Correct 103 ms 7220 KB Output is correct
86 Correct 12 ms 6944 KB Output is correct
87 Correct 13 ms 7236 KB Output is correct
88 Correct 11 ms 7136 KB Output is correct
89 Correct 12 ms 7112 KB Output is correct
90 Correct 36 ms 6688 KB Output is correct
91 Correct 42 ms 7160 KB Output is correct
92 Correct 127 ms 7316 KB Output is correct
93 Correct 20 ms 7244 KB Output is correct
94 Correct 11 ms 6964 KB Output is correct
95 Correct 14 ms 6896 KB Output is correct
96 Correct 11 ms 6668 KB Output is correct
97 Correct 38 ms 6688 KB Output is correct
98 Correct 38 ms 6772 KB Output is correct
99 Correct 23 ms 6784 KB Output is correct
100 Correct 57 ms 7108 KB Output is correct
101 Correct 21 ms 6988 KB Output is correct
102 Correct 48 ms 7116 KB Output is correct
103 Correct 11 ms 7096 KB Output is correct
104 Correct 11 ms 7116 KB Output is correct
105 Correct 12 ms 7256 KB Output is correct
106 Correct 12 ms 6872 KB Output is correct
107 Correct 13 ms 7340 KB Output is correct
108 Correct 11 ms 6988 KB Output is correct
109 Correct 12 ms 6988 KB Output is correct
110 Correct 16 ms 7116 KB Output is correct
111 Correct 12 ms 7064 KB Output is correct
112 Correct 11 ms 7320 KB Output is correct
113 Correct 11 ms 7108 KB Output is correct
114 Correct 11 ms 7204 KB Output is correct
115 Correct 11 ms 6988 KB Output is correct
116 Correct 11 ms 7328 KB Output is correct
117 Correct 11 ms 7008 KB Output is correct
118 Correct 11 ms 7328 KB Output is correct
119 Correct 11 ms 7024 KB Output is correct
120 Correct 13 ms 7360 KB Output is correct
121 Correct 179 ms 7268 KB Output is correct
122 Correct 173 ms 7268 KB Output is correct
123 Correct 74 ms 7096 KB Output is correct
124 Correct 11 ms 7244 KB Output is correct
125 Correct 11 ms 6940 KB Output is correct
126 Correct 16 ms 6820 KB Output is correct
127 Correct 250 ms 7492 KB Output is correct
128 Correct 9 ms 6168 KB Output is correct
129 Correct 123 ms 21256 KB Output is correct
130 Correct 129 ms 30736 KB Output is correct
131 Correct 135 ms 33608 KB Output is correct
132 Correct 98 ms 19716 KB Output is correct
133 Partially correct 103 ms 22632 KB Output is partially correct
134 Partially correct 104 ms 22812 KB Output is partially correct
135 Correct 124 ms 19656 KB Output is correct
136 Correct 134 ms 23640 KB Output is correct
137 Partially correct 95 ms 21036 KB Output is partially correct
138 Partially correct 103 ms 29464 KB Output is partially correct
139 Correct 361 ms 42668 KB Output is correct
140 Partially correct 345 ms 48708 KB Output is partially correct
141 Correct 381 ms 38204 KB Output is correct
142 Correct 524 ms 51908 KB Output is correct
143 Correct 486 ms 50512 KB Output is correct
144 Correct 468 ms 46148 KB Output is correct
145 Partially correct 430 ms 61068 KB Output is partially correct
146 Partially correct 297 ms 40732 KB Output is partially correct
147 Partially correct 369 ms 57044 KB Output is partially correct
148 Correct 684 ms 37908 KB Output is correct
149 Partially correct 102 ms 18912 KB Output is partially correct
150 Correct 134 ms 21508 KB Output is correct
151 Correct 125 ms 25580 KB Output is correct
152 Correct 122 ms 20812 KB Output is correct
153 Correct 138 ms 20416 KB Output is correct
154 Correct 149 ms 19780 KB Output is correct
155 Correct 132 ms 24736 KB Output is correct
156 Partially correct 96 ms 22636 KB Output is partially correct
157 Correct 92 ms 19220 KB Output is correct
158 Partially correct 96 ms 20968 KB Output is partially correct
159 Partially correct 94 ms 26764 KB Output is partially correct
160 Partially correct 280 ms 34984 KB Output is partially correct
161 Partially correct 362 ms 48812 KB Output is partially correct
162 Correct 567 ms 65908 KB Output is correct
163 Correct 493 ms 57164 KB Output is correct
164 Partially correct 444 ms 56644 KB Output is partially correct
165 Partially correct 449 ms 40904 KB Output is partially correct
166 Partially correct 391 ms 40912 KB Output is partially correct
167 Correct 613 ms 59628 KB Output is correct
168 Partially correct 306 ms 43756 KB Output is partially correct
169 Partially correct 293 ms 44692 KB Output is partially correct
170 Partially correct 271 ms 38588 KB Output is partially correct
171 Correct 431 ms 30228 KB Output is correct
172 Correct 571 ms 40192 KB Output is correct
173 Correct 489 ms 50756 KB Output is correct
174 Correct 444 ms 52040 KB Output is correct
175 Correct 419 ms 47172 KB Output is correct
176 Correct 409 ms 46240 KB Output is correct
177 Correct 406 ms 46464 KB Output is correct
178 Correct 556 ms 65408 KB Output is correct
179 Partially correct 349 ms 44688 KB Output is partially correct
180 Partially correct 329 ms 44996 KB Output is partially correct
181 Partially correct 344 ms 29528 KB Output is partially correct
182 Correct 514 ms 46624 KB Output is correct
183 Correct 527 ms 55736 KB Output is correct
184 Partially correct 431 ms 37624 KB Output is partially correct
185 Partially correct 435 ms 35348 KB Output is partially correct
186 Partially correct 363 ms 32700 KB Output is partially correct
187 Correct 1999 ms 128744 KB Output is correct
188 Partially correct 1446 ms 96616 KB Output is partially correct
189 Partially correct 1811 ms 120204 KB Output is partially correct
190 Partially correct 1406 ms 96556 KB Output is partially correct
191 Partially correct 1327 ms 97032 KB Output is partially correct
192 Partially correct 1426 ms 96936 KB Output is partially correct
193 Partially correct 1632 ms 111100 KB Output is partially correct
194 Correct 1561 ms 110620 KB Output is correct
195 Partially correct 1530 ms 91316 KB Output is partially correct
196 Partially correct 1431 ms 76472 KB Output is partially correct
197 Partially correct 1376 ms 75496 KB Output is partially correct
198 Partially correct 1534 ms 80892 KB Output is partially correct
199 Correct 1543 ms 74512 KB Output is correct
200 Partially correct 1444 ms 79640 KB Output is partially correct
201 Partially correct 1545 ms 75196 KB Output is partially correct
202 Correct 1925 ms 78744 KB Output is correct
203 Correct 1283 ms 85432 KB Output is correct
204 Correct 2433 ms 102144 KB Output is correct
205 Correct 2947 ms 102320 KB Output is correct
206 Correct 1973 ms 102104 KB Output is correct
207 Correct 2427 ms 102300 KB Output is correct
208 Correct 1494 ms 74620 KB Output is correct
209 Correct 2607 ms 132288 KB Output is correct
210 Partially correct 1363 ms 88204 KB Output is partially correct
211 Partially correct 1830 ms 100652 KB Output is partially correct
212 Correct 2084 ms 106104 KB Output is correct
213 Partially correct 1548 ms 88512 KB Output is partially correct
214 Partially correct 1730 ms 188844 KB Output is partially correct
215 Partially correct 1763 ms 181236 KB Output is partially correct
216 Correct 2304 ms 199856 KB Output is correct
217 Correct 1924 ms 77240 KB Output is correct
218 Correct 2420 ms 99356 KB Output is correct
219 Correct 1604 ms 112112 KB Output is correct
220 Partially correct 1652 ms 120388 KB Output is partially correct
221 Correct 1512 ms 83144 KB Output is correct
222 Partially correct 1483 ms 85184 KB Output is partially correct
223 Correct 2366 ms 163420 KB Output is correct
224 Correct 2461 ms 131372 KB Output is correct
225 Partially correct 1603 ms 112164 KB Output is partially correct
226 Partially correct 1851 ms 213848 KB Output is partially correct
227 Correct 2969 ms 98524 KB Output is correct
228 Correct 1996 ms 98720 KB Output is correct
229 Correct 1937 ms 129440 KB Output is correct
230 Partially correct 1561 ms 92020 KB Output is partially correct
231 Partially correct 1503 ms 81796 KB Output is partially correct
232 Partially correct 1561 ms 116236 KB Output is partially correct
233 Correct 2154 ms 180100 KB Output is correct
234 Correct 1665 ms 91756 KB Output is correct
235 Correct 1976 ms 154372 KB Output is correct
236 Correct 1791 ms 99792 KB Output is correct
237 Partially correct 1413 ms 79780 KB Output is partially correct
238 Correct 1818 ms 118296 KB Output is correct
239 Correct 1622 ms 103144 KB Output is correct
240 Correct 1595 ms 113196 KB Output is correct
241 Correct 1914 ms 146448 KB Output is correct
242 Correct 1805 ms 126408 KB Output is correct