oj.uz

Submission #504054

# Submission time Handle Problem Language Result Execution time Memory
504054 2022-01-09T15:17:59 Z rainboy Wells (CEOI21_wells) C
100 / 100
 2793 ms 212856 KB 
/* https://hsin.hr/ceoi/competition/ceoi2021_day2_editorial.pdf */
#include <stdio.h>

#define N	1500000
#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 solve() {
	static int aa[N + 1], 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;
}

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

	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])) {
			bad[r] = 1;
			return;
		}
}

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

	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);
	c = 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;
			if (!path[i])
				c++;
		} else if (min(g, l - 1 - g) + dd[i] + hh[i] >= k - 1)
			type[i] = 1;
		else
			type[i] = 0;
	}
	solve();
	deep = 0;
	for (i = 0; i < n; i++)
		if (dd[i] * 2 >= k - 1) {
			deep = 1;
			break;
		}
	if (deep)
		for (r = 0; r < k; r++)
			if (!bad[r])
				check(r);
	yes = 0, ans = 0;
	for (r = 0; r < k; r++)
		if (!bad[r])
			yes = 1, ans = (ans + xx[r]) % MD;
	ans = (long long) ans * pp2[c] % MD;
	printf(yes ? "YES\n" : "NO\n");
	printf("%d\n", ans);
	return 0;
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6148 KB Output is correct
2 Correct 8 ms 6220 KB Output is correct
3 Correct 9 ms 6168 KB Output is correct
4 Correct 8 ms 6160 KB Output is correct
5 Correct 8 ms 6220 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 9 ms 6292 KB Output is correct
8 Correct 8 ms 6220 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 8 ms 6268 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 8 ms 6344 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6164 KB Output is correct
17 Correct 9 ms 6208 KB Output is correct
18 Correct 8 ms 6168 KB Output is correct
19 Correct 8 ms 6264 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6272 KB Output is correct
22 Correct 8 ms 6208 KB Output is correct
23 Correct 9 ms 6160 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6276 KB Output is correct
26 Correct 10 ms 6220 KB Output is correct
27 Correct 8 ms 6284 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6212 KB Output is correct
30 Correct 9 ms 6220 KB Output is correct
31 Correct 8 ms 6280 KB Output is correct
32 Correct 9 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6292 KB Output is correct
35 Correct 8 ms 6220 KB Output is correct
36 Correct 8 ms 6164 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 8 ms 6288 KB Output is correct
39 Correct 8 ms 6156 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6292 KB Output is correct
42 Correct 9 ms 6160 KB Output is correct
43 Correct 8 ms 6348 KB Output is correct
44 Correct 9 ms 6164 KB Output is correct
45 Correct 8 ms 6220 KB Output is correct
46 Correct 8 ms 6292 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6292 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6208 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 ms 6296 KB Output is correct
53 Correct 9 ms 6276 KB Output is correct
54 Correct 8 ms 6212 KB Output is correct
55 Correct 8 ms 6152 KB Output is correct
56 Correct 8 ms 6164 KB Output is correct
57 Correct 8 ms 6292 KB Output is correct
58 Correct 8 ms 6220 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6148 KB Output is correct
2 Correct 8 ms 6220 KB Output is correct
3 Correct 9 ms 6168 KB Output is correct
4 Correct 8 ms 6160 KB Output is correct
5 Correct 8 ms 6220 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 9 ms 6292 KB Output is correct
8 Correct 8 ms 6220 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 8 ms 6268 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 8 ms 6344 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6164 KB Output is correct
17 Correct 9 ms 6208 KB Output is correct
18 Correct 8 ms 6168 KB Output is correct
19 Correct 8 ms 6264 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6272 KB Output is correct
22 Correct 8 ms 6208 KB Output is correct
23 Correct 9 ms 6160 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6276 KB Output is correct
26 Correct 10 ms 6220 KB Output is correct
27 Correct 8 ms 6284 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6212 KB Output is correct
30 Correct 9 ms 6220 KB Output is correct
31 Correct 8 ms 6280 KB Output is correct
32 Correct 9 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6292 KB Output is correct
35 Correct 8 ms 6220 KB Output is correct
36 Correct 8 ms 6164 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 8 ms 6288 KB Output is correct
39 Correct 8 ms 6156 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6292 KB Output is correct
42 Correct 9 ms 6160 KB Output is correct
43 Correct 8 ms 6348 KB Output is correct
44 Correct 9 ms 6164 KB Output is correct
45 Correct 8 ms 6220 KB Output is correct
46 Correct 8 ms 6292 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6292 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6208 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 ms 6296 KB Output is correct
53 Correct 9 ms 6276 KB Output is correct
54 Correct 8 ms 6212 KB Output is correct
55 Correct 8 ms 6152 KB Output is correct
56 Correct 8 ms 6164 KB Output is correct
57 Correct 8 ms 6292 KB Output is correct
58 Correct 8 ms 6220 KB Output is correct
59 Correct 8 ms 6148 KB Output is correct
60 Correct 8 ms 6556 KB Output is correct
61 Correct 9 ms 6412 KB Output is correct
62 Correct 10 ms 6556 KB Output is correct
63 Correct 11 ms 7096 KB Output is correct
64 Correct 11 ms 7576 KB Output is correct
65 Correct 11 ms 6948 KB Output is correct
66 Correct 12 ms 6948 KB Output is correct
67 Correct 12 ms 7316 KB Output is correct
68 Correct 9 ms 6684 KB Output is correct
69 Correct 11 ms 6432 KB Output is correct
70 Correct 10 ms 6656 KB Output is correct
71 Correct 10 ms 6688 KB Output is correct
72 Correct 10 ms 6604 KB Output is correct
73 Correct 9 ms 6644 KB Output is correct
74 Correct 10 ms 7068 KB Output is correct
75 Correct 11 ms 6808 KB Output is correct
76 Correct 12 ms 6936 KB Output is correct
77 Correct 9 ms 6472 KB Output is correct
78 Correct 9 ms 6476 KB Output is correct
79 Correct 10 ms 6540 KB Output is correct
80 Correct 10 ms 6936 KB Output is correct
81 Correct 11 ms 6940 KB Output is correct
82 Correct 10 ms 6860 KB Output is correct
83 Correct 14 ms 6920 KB Output is correct
84 Correct 11 ms 6852 KB Output is correct
85 Correct 10 ms 7116 KB Output is correct
86 Correct 10 ms 6860 KB Output is correct
87 Correct 12 ms 7192 KB Output is correct
88 Correct 12 ms 7244 KB Output is correct
89 Correct 11 ms 7064 KB Output is correct
90 Correct 10 ms 6552 KB Output is correct
91 Correct 11 ms 6988 KB Output is correct
92 Correct 11 ms 7108 KB Output is correct
93 Correct 11 ms 7072 KB Output is correct
94 Correct 14 ms 6788 KB Output is correct
95 Correct 11 ms 6824 KB Output is correct
96 Correct 10 ms 6604 KB Output is correct
97 Correct 10 ms 6768 KB Output is correct
98 Correct 10 ms 6752 KB Output is correct
99 Correct 10 ms 6600 KB Output is correct
100 Correct 11 ms 6968 KB Output is correct
101 Correct 12 ms 6744 KB Output is correct
102 Correct 11 ms 7076 KB Output is correct
103 Correct 10 ms 6872 KB Output is correct
104 Correct 12 ms 6988 KB Output is correct
105 Correct 12 ms 7244 KB Output is correct
106 Correct 12 ms 6880 KB Output is correct
107 Correct 12 ms 7340 KB Output is correct
108 Correct 12 ms 7064 KB Output is correct
109 Correct 12 ms 7016 KB Output is correct
110 Correct 11 ms 6988 KB Output is correct
111 Correct 11 ms 7068 KB Output is correct
112 Correct 13 ms 7252 KB Output is correct
113 Correct 11 ms 7052 KB Output is correct
114 Correct 11 ms 7176 KB Output is correct
115 Correct 11 ms 6988 KB Output is correct
116 Correct 11 ms 7312 KB Output is correct
117 Correct 12 ms 6980 KB Output is correct
118 Correct 14 ms 7320 KB Output is correct
119 Correct 11 ms 7068 KB Output is correct
120 Correct 11 ms 7188 KB Output is correct
121 Correct 11 ms 7064 KB Output is correct
122 Correct 10 ms 7008 KB Output is correct
123 Correct 12 ms 6920 KB Output is correct
124 Correct 12 ms 7320 KB Output is correct
125 Correct 11 ms 6888 KB Output is correct
126 Correct 10 ms 6820 KB Output is correct
127 Correct 11 ms 7216 KB Output is correct

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6148 KB Output is correct
2 Correct 8 ms 6220 KB Output is correct
3 Correct 9 ms 6168 KB Output is correct
4 Correct 8 ms 6160 KB Output is correct
5 Correct 8 ms 6220 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 9 ms 6292 KB Output is correct
8 Correct 8 ms 6220 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 8 ms 6268 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 8 ms 6344 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6164 KB Output is correct
17 Correct 9 ms 6208 KB Output is correct
18 Correct 8 ms 6168 KB Output is correct
19 Correct 8 ms 6264 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6272 KB Output is correct
22 Correct 8 ms 6208 KB Output is correct
23 Correct 9 ms 6160 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6276 KB Output is correct
26 Correct 10 ms 6220 KB Output is correct
27 Correct 8 ms 6284 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6212 KB Output is correct
30 Correct 9 ms 6220 KB Output is correct
31 Correct 8 ms 6280 KB Output is correct
32 Correct 9 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6292 KB Output is correct
35 Correct 8 ms 6220 KB Output is correct
36 Correct 8 ms 6164 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 8 ms 6288 KB Output is correct
39 Correct 8 ms 6156 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6292 KB Output is correct
42 Correct 9 ms 6160 KB Output is correct
43 Correct 8 ms 6348 KB Output is correct
44 Correct 9 ms 6164 KB Output is correct
45 Correct 8 ms 6220 KB Output is correct
46 Correct 8 ms 6292 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6292 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6208 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 ms 6296 KB Output is correct
53 Correct 9 ms 6276 KB Output is correct
54 Correct 8 ms 6212 KB Output is correct
55 Correct 8 ms 6152 KB Output is correct
56 Correct 8 ms 6164 KB Output is correct
57 Correct 8 ms 6292 KB Output is correct
58 Correct 8 ms 6220 KB Output is correct
59 Correct 8 ms 6148 KB Output is correct
60 Correct 8 ms 6556 KB Output is correct
61 Correct 9 ms 6412 KB Output is correct
62 Correct 10 ms 6556 KB Output is correct
63 Correct 11 ms 7096 KB Output is correct
64 Correct 11 ms 7576 KB Output is correct
65 Correct 11 ms 6948 KB Output is correct
66 Correct 12 ms 6948 KB Output is correct
67 Correct 12 ms 7316 KB Output is correct
68 Correct 9 ms 6684 KB Output is correct
69 Correct 11 ms 6432 KB Output is correct
70 Correct 10 ms 6656 KB Output is correct
71 Correct 10 ms 6688 KB Output is correct
72 Correct 10 ms 6604 KB Output is correct
73 Correct 9 ms 6644 KB Output is correct
74 Correct 10 ms 7068 KB Output is correct
75 Correct 11 ms 6808 KB Output is correct
76 Correct 12 ms 6936 KB Output is correct
77 Correct 9 ms 6472 KB Output is correct
78 Correct 9 ms 6476 KB Output is correct
79 Correct 10 ms 6540 KB Output is correct
80 Correct 10 ms 6936 KB Output is correct
81 Correct 11 ms 6940 KB Output is correct
82 Correct 10 ms 6860 KB Output is correct
83 Correct 14 ms 6920 KB Output is correct
84 Correct 11 ms 6852 KB Output is correct
85 Correct 10 ms 7116 KB Output is correct
86 Correct 10 ms 6860 KB Output is correct
87 Correct 12 ms 7192 KB Output is correct
88 Correct 12 ms 7244 KB Output is correct
89 Correct 11 ms 7064 KB Output is correct
90 Correct 10 ms 6552 KB Output is correct
91 Correct 11 ms 6988 KB Output is correct
92 Correct 11 ms 7108 KB Output is correct
93 Correct 11 ms 7072 KB Output is correct
94 Correct 14 ms 6788 KB Output is correct
95 Correct 11 ms 6824 KB Output is correct
96 Correct 10 ms 6604 KB Output is correct
97 Correct 10 ms 6768 KB Output is correct
98 Correct 10 ms 6752 KB Output is correct
99 Correct 10 ms 6600 KB Output is correct
100 Correct 11 ms 6968 KB Output is correct
101 Correct 12 ms 6744 KB Output is correct
102 Correct 11 ms 7076 KB Output is correct
103 Correct 10 ms 6872 KB Output is correct
104 Correct 12 ms 6988 KB Output is correct
105 Correct 12 ms 7244 KB Output is correct
106 Correct 12 ms 6880 KB Output is correct
107 Correct 12 ms 7340 KB Output is correct
108 Correct 12 ms 7064 KB Output is correct
109 Correct 12 ms 7016 KB Output is correct
110 Correct 11 ms 6988 KB Output is correct
111 Correct 11 ms 7068 KB Output is correct
112 Correct 13 ms 7252 KB Output is correct
113 Correct 11 ms 7052 KB Output is correct
114 Correct 11 ms 7176 KB Output is correct
115 Correct 11 ms 6988 KB Output is correct
116 Correct 11 ms 7312 KB Output is correct
117 Correct 12 ms 6980 KB Output is correct
118 Correct 14 ms 7320 KB Output is correct
119 Correct 11 ms 7068 KB Output is correct
120 Correct 11 ms 7188 KB Output is correct
121 Correct 11 ms 7064 KB Output is correct
122 Correct 10 ms 7008 KB Output is correct
123 Correct 12 ms 6920 KB Output is correct
124 Correct 12 ms 7320 KB Output is correct
125 Correct 11 ms 6888 KB Output is correct
126 Correct 10 ms 6820 KB Output is correct
127 Correct 11 ms 7216 KB Output is correct
128 Correct 8 ms 6168 KB Output is correct
129 Correct 122 ms 21172 KB Output is correct
130 Correct 132 ms 30656 KB Output is correct
131 Correct 121 ms 33440 KB Output is correct
132 Correct 95 ms 19652 KB Output is correct
133 Correct 108 ms 22596 KB Output is correct
134 Correct 103 ms 22576 KB Output is correct
135 Correct 159 ms 19560 KB Output is correct
136 Correct 131 ms 23572 KB Output is correct
137 Correct 93 ms 21060 KB Output is correct
138 Correct 98 ms 29328 KB Output is correct
139 Correct 321 ms 42536 KB Output is correct
140 Correct 360 ms 48708 KB Output is correct
141 Correct 383 ms 38212 KB Output is correct
142 Correct 539 ms 51936 KB Output is correct
143 Correct 503 ms 50648 KB Output is correct
144 Correct 459 ms 46048 KB Output is correct
145 Correct 466 ms 61068 KB Output is correct
146 Correct 307 ms 40644 KB Output is correct
147 Correct 362 ms 57092 KB Output is correct
148 Correct 694 ms 37856 KB Output is correct
149 Correct 109 ms 18892 KB Output is correct
150 Correct 138 ms 21340 KB Output is correct
151 Correct 144 ms 25616 KB Output is correct
152 Correct 132 ms 20632 KB Output is correct
153 Correct 151 ms 20320 KB Output is correct
154 Correct 145 ms 19780 KB Output is correct
155 Correct 130 ms 24676 KB Output is correct
156 Correct 102 ms 22588 KB Output is correct
157 Correct 106 ms 19208 KB Output is correct
158 Correct 103 ms 20872 KB Output is correct
159 Correct 96 ms 26692 KB Output is correct
160 Correct 286 ms 34916 KB Output is correct
161 Correct 347 ms 48816 KB Output is correct
162 Correct 583 ms 65816 KB Output is correct
163 Correct 504 ms 57092 KB Output is correct
164 Correct 493 ms 56704 KB Output is correct
165 Correct 477 ms 40884 KB Output is correct
166 Correct 396 ms 40884 KB Output is correct
167 Correct 647 ms 59620 KB Output is correct
168 Correct 323 ms 43972 KB Output is correct
169 Correct 287 ms 44624 KB Output is correct
170 Correct 264 ms 38632 KB Output is correct
171 Correct 432 ms 30280 KB Output is correct
172 Correct 570 ms 40252 KB Output is correct
173 Correct 472 ms 50880 KB Output is correct
174 Correct 433 ms 52020 KB Output is correct
175 Correct 415 ms 47112 KB Output is correct
176 Correct 411 ms 46108 KB Output is correct
177 Correct 411 ms 46384 KB Output is correct
178 Correct 558 ms 65464 KB Output is correct
179 Correct 307 ms 44356 KB Output is correct
180 Correct 294 ms 44004 KB Output is correct
181 Correct 278 ms 28356 KB Output is correct
182 Correct 391 ms 45336 KB Output is correct
183 Correct 426 ms 54764 KB Output is correct
184 Correct 352 ms 36932 KB Output is correct
185 Correct 349 ms 34556 KB Output is correct
186 Correct 299 ms 32084 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 6148 KB Output is correct
2 Correct 8 ms 6220 KB Output is correct
3 Correct 9 ms 6168 KB Output is correct
4 Correct 8 ms 6160 KB Output is correct
5 Correct 8 ms 6220 KB Output is correct
6 Correct 8 ms 6220 KB Output is correct
7 Correct 9 ms 6292 KB Output is correct
8 Correct 8 ms 6220 KB Output is correct
9 Correct 8 ms 6220 KB Output is correct
10 Correct 8 ms 6220 KB Output is correct
11 Correct 8 ms 6268 KB Output is correct
12 Correct 9 ms 6220 KB Output is correct
13 Correct 8 ms 6292 KB Output is correct
14 Correct 8 ms 6344 KB Output is correct
15 Correct 9 ms 6220 KB Output is correct
16 Correct 8 ms 6164 KB Output is correct
17 Correct 9 ms 6208 KB Output is correct
18 Correct 8 ms 6168 KB Output is correct
19 Correct 8 ms 6264 KB Output is correct
20 Correct 8 ms 6220 KB Output is correct
21 Correct 8 ms 6272 KB Output is correct
22 Correct 8 ms 6208 KB Output is correct
23 Correct 9 ms 6160 KB Output is correct
24 Correct 8 ms 6220 KB Output is correct
25 Correct 8 ms 6276 KB Output is correct
26 Correct 10 ms 6220 KB Output is correct
27 Correct 8 ms 6284 KB Output is correct
28 Correct 8 ms 6220 KB Output is correct
29 Correct 8 ms 6212 KB Output is correct
30 Correct 9 ms 6220 KB Output is correct
31 Correct 8 ms 6280 KB Output is correct
32 Correct 9 ms 6220 KB Output is correct
33 Correct 8 ms 6292 KB Output is correct
34 Correct 8 ms 6292 KB Output is correct
35 Correct 8 ms 6220 KB Output is correct
36 Correct 8 ms 6164 KB Output is correct
37 Correct 9 ms 6220 KB Output is correct
38 Correct 8 ms 6288 KB Output is correct
39 Correct 8 ms 6156 KB Output is correct
40 Correct 8 ms 6220 KB Output is correct
41 Correct 8 ms 6292 KB Output is correct
42 Correct 9 ms 6160 KB Output is correct
43 Correct 8 ms 6348 KB Output is correct
44 Correct 9 ms 6164 KB Output is correct
45 Correct 8 ms 6220 KB Output is correct
46 Correct 8 ms 6292 KB Output is correct
47 Correct 8 ms 6220 KB Output is correct
48 Correct 8 ms 6292 KB Output is correct
49 Correct 8 ms 6220 KB Output is correct
50 Correct 8 ms 6208 KB Output is correct
51 Correct 8 ms 6220 KB Output is correct
52 Correct 8 ms 6296 KB Output is correct
53 Correct 9 ms 6276 KB Output is correct
54 Correct 8 ms 6212 KB Output is correct
55 Correct 8 ms 6152 KB Output is correct
56 Correct 8 ms 6164 KB Output is correct
57 Correct 8 ms 6292 KB Output is correct
58 Correct 8 ms 6220 KB Output is correct
59 Correct 8 ms 6148 KB Output is correct
60 Correct 8 ms 6556 KB Output is correct
61 Correct 9 ms 6412 KB Output is correct
62 Correct 10 ms 6556 KB Output is correct
63 Correct 11 ms 7096 KB Output is correct
64 Correct 11 ms 7576 KB Output is correct
65 Correct 11 ms 6948 KB Output is correct
66 Correct 12 ms 6948 KB Output is correct
67 Correct 12 ms 7316 KB Output is correct
68 Correct 9 ms 6684 KB Output is correct
69 Correct 11 ms 6432 KB Output is correct
70 Correct 10 ms 6656 KB Output is correct
71 Correct 10 ms 6688 KB Output is correct
72 Correct 10 ms 6604 KB Output is correct
73 Correct 9 ms 6644 KB Output is correct
74 Correct 10 ms 7068 KB Output is correct
75 Correct 11 ms 6808 KB Output is correct
76 Correct 12 ms 6936 KB Output is correct
77 Correct 9 ms 6472 KB Output is correct
78 Correct 9 ms 6476 KB Output is correct
79 Correct 10 ms 6540 KB Output is correct
80 Correct 10 ms 6936 KB Output is correct
81 Correct 11 ms 6940 KB Output is correct
82 Correct 10 ms 6860 KB Output is correct
83 Correct 14 ms 6920 KB Output is correct
84 Correct 11 ms 6852 KB Output is correct
85 Correct 10 ms 7116 KB Output is correct
86 Correct 10 ms 6860 KB Output is correct
87 Correct 12 ms 7192 KB Output is correct
88 Correct 12 ms 7244 KB Output is correct
89 Correct 11 ms 7064 KB Output is correct
90 Correct 10 ms 6552 KB Output is correct
91 Correct 11 ms 6988 KB Output is correct
92 Correct 11 ms 7108 KB Output is correct
93 Correct 11 ms 7072 KB Output is correct
94 Correct 14 ms 6788 KB Output is correct
95 Correct 11 ms 6824 KB Output is correct
96 Correct 10 ms 6604 KB Output is correct
97 Correct 10 ms 6768 KB Output is correct
98 Correct 10 ms 6752 KB Output is correct
99 Correct 10 ms 6600 KB Output is correct
100 Correct 11 ms 6968 KB Output is correct
101 Correct 12 ms 6744 KB Output is correct
102 Correct 11 ms 7076 KB Output is correct
103 Correct 10 ms 6872 KB Output is correct
104 Correct 12 ms 6988 KB Output is correct
105 Correct 12 ms 7244 KB Output is correct
106 Correct 12 ms 6880 KB Output is correct
107 Correct 12 ms 7340 KB Output is correct
108 Correct 12 ms 7064 KB Output is correct
109 Correct 12 ms 7016 KB Output is correct
110 Correct 11 ms 6988 KB Output is correct
111 Correct 11 ms 7068 KB Output is correct
112 Correct 13 ms 7252 KB Output is correct
113 Correct 11 ms 7052 KB Output is correct
114 Correct 11 ms 7176 KB Output is correct
115 Correct 11 ms 6988 KB Output is correct
116 Correct 11 ms 7312 KB Output is correct
117 Correct 12 ms 6980 KB Output is correct
118 Correct 14 ms 7320 KB Output is correct
119 Correct 11 ms 7068 KB Output is correct
120 Correct 11 ms 7188 KB Output is correct
121 Correct 11 ms 7064 KB Output is correct
122 Correct 10 ms 7008 KB Output is correct
123 Correct 12 ms 6920 KB Output is correct
124 Correct 12 ms 7320 KB Output is correct
125 Correct 11 ms 6888 KB Output is correct
126 Correct 10 ms 6820 KB Output is correct
127 Correct 11 ms 7216 KB Output is correct
128 Correct 8 ms 6168 KB Output is correct
129 Correct 122 ms 21172 KB Output is correct
130 Correct 132 ms 30656 KB Output is correct
131 Correct 121 ms 33440 KB Output is correct
132 Correct 95 ms 19652 KB Output is correct
133 Correct 108 ms 22596 KB Output is correct
134 Correct 103 ms 22576 KB Output is correct
135 Correct 159 ms 19560 KB Output is correct
136 Correct 131 ms 23572 KB Output is correct
137 Correct 93 ms 21060 KB Output is correct
138 Correct 98 ms 29328 KB Output is correct
139 Correct 321 ms 42536 KB Output is correct
140 Correct 360 ms 48708 KB Output is correct
141 Correct 383 ms 38212 KB Output is correct
142 Correct 539 ms 51936 KB Output is correct
143 Correct 503 ms 50648 KB Output is correct
144 Correct 459 ms 46048 KB Output is correct
145 Correct 466 ms 61068 KB Output is correct
146 Correct 307 ms 40644 KB Output is correct
147 Correct 362 ms 57092 KB Output is correct
148 Correct 694 ms 37856 KB Output is correct
149 Correct 109 ms 18892 KB Output is correct
150 Correct 138 ms 21340 KB Output is correct
151 Correct 144 ms 25616 KB Output is correct
152 Correct 132 ms 20632 KB Output is correct
153 Correct 151 ms 20320 KB Output is correct
154 Correct 145 ms 19780 KB Output is correct
155 Correct 130 ms 24676 KB Output is correct
156 Correct 102 ms 22588 KB Output is correct
157 Correct 106 ms 19208 KB Output is correct
158 Correct 103 ms 20872 KB Output is correct
159 Correct 96 ms 26692 KB Output is correct
160 Correct 286 ms 34916 KB Output is correct
161 Correct 347 ms 48816 KB Output is correct
162 Correct 583 ms 65816 KB Output is correct
163 Correct 504 ms 57092 KB Output is correct
164 Correct 493 ms 56704 KB Output is correct
165 Correct 477 ms 40884 KB Output is correct
166 Correct 396 ms 40884 KB Output is correct
167 Correct 647 ms 59620 KB Output is correct
168 Correct 323 ms 43972 KB Output is correct
169 Correct 287 ms 44624 KB Output is correct
170 Correct 264 ms 38632 KB Output is correct
171 Correct 432 ms 30280 KB Output is correct
172 Correct 570 ms 40252 KB Output is correct
173 Correct 472 ms 50880 KB Output is correct
174 Correct 433 ms 52020 KB Output is correct
175 Correct 415 ms 47112 KB Output is correct
176 Correct 411 ms 46108 KB Output is correct
177 Correct 411 ms 46384 KB Output is correct
178 Correct 558 ms 65464 KB Output is correct
179 Correct 307 ms 44356 KB Output is correct
180 Correct 294 ms 44004 KB Output is correct
181 Correct 278 ms 28356 KB Output is correct
182 Correct 391 ms 45336 KB Output is correct
183 Correct 426 ms 54764 KB Output is correct
184 Correct 352 ms 36932 KB Output is correct
185 Correct 349 ms 34556 KB Output is correct
186 Correct 299 ms 32084 KB Output is correct
187 Correct 1745 ms 128048 KB Output is correct
188 Correct 1228 ms 96004 KB Output is correct
189 Correct 1709 ms 119800 KB Output is correct
190 Correct 1301 ms 96092 KB Output is correct
191 Correct 1250 ms 96504 KB Output is correct
192 Correct 1251 ms 96072 KB Output is correct
193 Correct 1524 ms 110252 KB Output is correct
194 Correct 1493 ms 109988 KB Output is correct
195 Correct 1450 ms 90908 KB Output is correct
196 Correct 1345 ms 76060 KB Output is correct
197 Correct 1292 ms 75380 KB Output is correct
198 Correct 1332 ms 80508 KB Output is correct
199 Correct 1466 ms 73960 KB Output is correct
200 Correct 1341 ms 79116 KB Output is correct
201 Correct 1398 ms 74688 KB Output is correct
202 Correct 1805 ms 78232 KB Output is correct
203 Correct 1219 ms 84876 KB Output is correct
204 Correct 2305 ms 101684 KB Output is correct
205 Correct 2793 ms 102004 KB Output is correct
206 Correct 1837 ms 101756 KB Output is correct
207 Correct 2277 ms 101796 KB Output is correct
208 Correct 1382 ms 74136 KB Output is correct
209 Correct 2487 ms 132160 KB Output is correct
210 Correct 1280 ms 87808 KB Output is correct
211 Correct 1677 ms 100256 KB Output is correct
212 Correct 1830 ms 105160 KB Output is correct
213 Correct 1362 ms 87596 KB Output is correct
214 Correct 1547 ms 187976 KB Output is correct
215 Correct 1638 ms 180524 KB Output is correct
216 Correct 2243 ms 198788 KB Output is correct
217 Correct 1834 ms 76188 KB Output is correct
218 Correct 2320 ms 98288 KB Output is correct
219 Correct 1484 ms 111196 KB Output is correct
220 Correct 1544 ms 119596 KB Output is correct
221 Correct 1438 ms 82080 KB Output is correct
222 Correct 1405 ms 84192 KB Output is correct
223 Correct 2159 ms 162564 KB Output is correct
224 Correct 2270 ms 130480 KB Output is correct
225 Correct 1465 ms 111128 KB Output is correct
226 Correct 1710 ms 212856 KB Output is correct
227 Correct 2739 ms 97624 KB Output is correct
228 Correct 1802 ms 97904 KB Output is correct
229 Correct 1864 ms 129240 KB Output is correct
230 Correct 1485 ms 91168 KB Output is correct
231 Correct 1438 ms 81140 KB Output is correct
232 Correct 1469 ms 115344 KB Output is correct
233 Correct 2097 ms 179288 KB Output is correct
234 Correct 1512 ms 90968 KB Output is correct
235 Correct 1854 ms 153376 KB Output is correct
236 Correct 1686 ms 99120 KB Output is correct
237 Correct 1297 ms 78868 KB Output is correct
238 Correct 1702 ms 117648 KB Output is correct
239 Correct 1568 ms 102380 KB Output is correct
240 Correct 1485 ms 112140 KB Output is correct
241 Correct 1838 ms 145732 KB Output is correct
242 Correct 1680 ms 126152 KB Output is correct