Submission #528280

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
528280	2022-02-19T19:14:23 Z	rainboy	Parkovi (COCI22_parkovi)	C	110 / 110	2310 ms	34024 KB

Main

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

#define N	200000
#define INF	0x3f3f3f3f3f3f3f3fLL

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

int ij[N - 1], ww[N - 1];
int *eh[N], eo[N];

void append(int i, int h) {
	int o = eo[i]++;

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

long long dp[N], dq[N], r; int qu[N], cnt;

void dfs(int f, int i) {
	int o;

	dp[i] = INF, dq[i] = 0;
	for (o = eo[i]; o--; ) {
		int h = eh[i][o], j = i ^ ij[h];

		if (h != f) {
			dfs(h, j);
			dp[i] = min(dp[i], dp[j]), dq[i] = max(dq[i], dq[j]);
		}
	}
	if (dp[i] + dq[i] <= r)
		dq[i] = -INF;
	if (dq[i] != -INF && (f == -1 || dq[i] + ww[f] > r))
		qu[cnt++] = i, dp[i] = 0, dq[i] = -INF;
	if (dp[i] != INF && f != -1)
		dp[i] += ww[f];
	if (dq[i] != -INF && f != -1)
		dq[i] += ww[f];
}

int main() {
	static char used[N];
	int n, k, h, i, j;
	long long lower, upper;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		eh[i] = (int *) malloc(2 * sizeof *eh[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d%d", &i, &j, &ww[h]), i--, j--;
		ij[h] = i ^ j;
		append(i, h), append(j, h);
	}
	lower = -1, upper = INF;
	while (upper - lower > 1) {
		r = (lower + upper) / 2;
		cnt = 0, dfs(-1, 0);
		if (cnt <= k)
			upper = r;
		else
			lower = r;
	}
	r = upper;
	cnt = 0, dfs(-1, 0);
	k -= cnt;
	while (cnt--)
		used[qu[cnt]] = 1;
	for (i = 0; i < n && k > 0; i++)
		if (!used[i])
			used[i] = 1, k--;
	printf("%lld\n", upper);
	for (i = 0; i < n; i++)
		if (used[i])
			printf("%d ", i + 1);
	printf("\n");
	return 0;
}

Compilation message

Main.c: In function 'append':
Main.c:16:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   16 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.c: In function 'main':
Main.c:50:2: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &k);
      |  ^~~~~~~~~~~~~~~~~~~~~
Main.c:54:3: warning: ignoring return value of 'scanf' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |   scanf("%d%d%d", &i, &j, &ww[h]), i--, j--;
      |   ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	264 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	284 KB	Output is correct
12	Correct	0 ms	280 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	0 ms	276 KB	Output is correct

Subtask #2

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	396 ms	30048 KB	Output is correct
2	Correct	455 ms	30356 KB	Output is correct
3	Correct	674 ms	18992 KB	Output is correct
4	Correct	1848 ms	17128 KB	Output is correct
5	Correct	2001 ms	16520 KB	Output is correct
6	Correct	1771 ms	16620 KB	Output is correct
7	Correct	2028 ms	15516 KB	Output is correct
8	Correct	2310 ms	14940 KB	Output is correct
9	Correct	2012 ms	13272 KB	Output is correct
10	Correct	1883 ms	16948 KB	Output is correct
11	Correct	1312 ms	17656 KB	Output is correct
12	Correct	1198 ms	17808 KB	Output is correct
13	Correct	1496 ms	19584 KB	Output is correct
14	Correct	1358 ms	16652 KB	Output is correct
15	Correct	1316 ms	16284 KB	Output is correct
16	Correct	1353 ms	17692 KB	Output is correct
17	Correct	1362 ms	16952 KB	Output is correct

Subtask #3

30.0 / 30.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	442 ms	32300 KB	Output is correct
2	Correct	438 ms	31836 KB	Output is correct
3	Correct	413 ms	30180 KB	Output is correct
4	Correct	394 ms	30052 KB	Output is correct
5	Correct	433 ms	33248 KB	Output is correct
6	Correct	541 ms	32756 KB	Output is correct
7	Correct	484 ms	34024 KB	Output is correct
8	Correct	455 ms	32316 KB	Output is correct
9	Correct	444 ms	32044 KB	Output is correct
10	Correct	412 ms	29368 KB	Output is correct
11	Correct	405 ms	27008 KB	Output is correct
12	Correct	503 ms	30660 KB	Output is correct
13	Correct	527 ms	30532 KB	Output is correct
14	Correct	474 ms	29452 KB	Output is correct
15	Correct	401 ms	28032 KB	Output is correct
16	Correct	408 ms	26856 KB	Output is correct
17	Correct	387 ms	26764 KB	Output is correct
18	Correct	415 ms	28228 KB	Output is correct
19	Correct	420 ms	28696 KB	Output is correct
20	Correct	422 ms	29260 KB	Output is correct
21	Correct	444 ms	28484 KB	Output is correct

Subtask #4

60.0 / 60.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	204 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	0 ms	264 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	204 KB	Output is correct
6	Correct	1 ms	332 KB	Output is correct
7	Correct	1 ms	204 KB	Output is correct
8	Correct	0 ms	204 KB	Output is correct
9	Correct	0 ms	332 KB	Output is correct
10	Correct	0 ms	332 KB	Output is correct
11	Correct	0 ms	284 KB	Output is correct
12	Correct	0 ms	280 KB	Output is correct
13	Correct	0 ms	332 KB	Output is correct
14	Correct	0 ms	276 KB	Output is correct
15	Correct	396 ms	30048 KB	Output is correct
16	Correct	455 ms	30356 KB	Output is correct
17	Correct	674 ms	18992 KB	Output is correct
18	Correct	1848 ms	17128 KB	Output is correct
19	Correct	2001 ms	16520 KB	Output is correct
20	Correct	1771 ms	16620 KB	Output is correct
21	Correct	2028 ms	15516 KB	Output is correct
22	Correct	2310 ms	14940 KB	Output is correct
23	Correct	2012 ms	13272 KB	Output is correct
24	Correct	1883 ms	16948 KB	Output is correct
25	Correct	1312 ms	17656 KB	Output is correct
26	Correct	1198 ms	17808 KB	Output is correct
27	Correct	1496 ms	19584 KB	Output is correct
28	Correct	1358 ms	16652 KB	Output is correct
29	Correct	1316 ms	16284 KB	Output is correct
30	Correct	1353 ms	17692 KB	Output is correct
31	Correct	1362 ms	16952 KB	Output is correct
32	Correct	442 ms	32300 KB	Output is correct
33	Correct	438 ms	31836 KB	Output is correct
34	Correct	413 ms	30180 KB	Output is correct
35	Correct	394 ms	30052 KB	Output is correct
36	Correct	433 ms	33248 KB	Output is correct
37	Correct	541 ms	32756 KB	Output is correct
38	Correct	484 ms	34024 KB	Output is correct
39	Correct	455 ms	32316 KB	Output is correct
40	Correct	444 ms	32044 KB	Output is correct
41	Correct	412 ms	29368 KB	Output is correct
42	Correct	405 ms	27008 KB	Output is correct
43	Correct	503 ms	30660 KB	Output is correct
44	Correct	527 ms	30532 KB	Output is correct
45	Correct	474 ms	29452 KB	Output is correct
46	Correct	401 ms	28032 KB	Output is correct
47	Correct	408 ms	26856 KB	Output is correct
48	Correct	387 ms	26764 KB	Output is correct
49	Correct	415 ms	28228 KB	Output is correct
50	Correct	420 ms	28696 KB	Output is correct
51	Correct	422 ms	29260 KB	Output is correct
52	Correct	444 ms	28484 KB	Output is correct
53	Correct	1884 ms	13144 KB	Output is correct
54	Correct	1930 ms	13528 KB	Output is correct
55	Correct	2103 ms	14092 KB	Output is correct
56	Correct	1931 ms	13976 KB	Output is correct
57	Correct	2044 ms	14800 KB	Output is correct
58	Correct	1992 ms	13256 KB	Output is correct
59	Correct	2225 ms	15932 KB	Output is correct
60	Correct	1977 ms	14052 KB	Output is correct
61	Correct	1780 ms	12832 KB	Output is correct
62	Correct	1728 ms	14040 KB	Output is correct
63	Correct	2029 ms	14104 KB	Output is correct
64	Correct	1854 ms	15308 KB	Output is correct
65	Correct	2025 ms	13708 KB	Output is correct
66	Correct	1952 ms	14276 KB	Output is correct
67	Correct	1820 ms	12924 KB	Output is correct
68	Correct	2071 ms	16016 KB	Output is correct
69	Correct	414 ms	28116 KB	Output is correct
70	Correct	427 ms	26668 KB	Output is correct
71	Correct	485 ms	30044 KB	Output is correct
72	Correct	597 ms	13908 KB	Output is correct
73	Correct	663 ms	14276 KB	Output is correct
74	Correct	650 ms	15568 KB	Output is correct
75	Correct	1445 ms	14704 KB	Output is correct
76	Correct	1464 ms	15380 KB	Output is correct
77	Correct	1391 ms	14640 KB	Output is correct
78	Correct	1507 ms	15432 KB	Output is correct