Submission #528280

#	Time	Username	Problem	Language	Result	Execution time	Memory
528280		rainboy	Parkovi (COCI22_parkovi)	C11	110 / 110	2310 ms	34024 KiB

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 (stderr)

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 / 10
• Subtask 2: 10 / 10
• Subtask 3: 30 / 30
• Subtask 4: 60 / 60