Submission #823991

#	Time	Username	Problem	Language	Result	Execution time	Memory
823991		rainboy	Travelling Trader (CCO23_day2problem2)	C11	11 / 25	129 ms	29732 KiB

Main

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

#define N	200000

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

int *ej[N], eo[N], ww[N], n;

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

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

long long dp[N], dq[N]; int jj[N], jjp1[N], jjp2[N], jjq[N];
int qu[N], cnt;

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

	j_ = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs1(i, j);
			if (j_ == -1 || dp[j_] < dp[j])
				j_ = j;
		}
	}
	jj[i] = j_, dp[i] = (j_ == -1 ? 0 : dp[j_]) + ww[i];
}

void dfs1_(int i) {
	qu[cnt++] = i;
	if (jj[i] != -1)
		dfs1_(jj[i]);
}

void dfs2(int p, int i) {
	int o, jp1, jp2, jp, jq;
	long long w, x, x_;

	w = 0, jp1 = jp2 = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			dfs2(i, j);
			w += ww[j];
			if (jp1 == -1 || dp[jp1] < dp[j])
				jp2 = jp1, jp1 = j;
			else if (jp2 == -1 || dp[jp2] < dp[j])
				jp2 = j;
		}
	}
	jjp1[i] = jp1, jjp2[i] = jp2, dp[i] = (jp1 == -1 ? 0 : dp[jp1]) + w;
	x_ = -1, jq = -1;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p) {
			jp = j != jp1 ? jp1 : jp2;
			x = (jp == -1 ? 0 : dp[jp]) + dq[j];
			if (x_ < x)
				x_ = x, jq = j;
		}
	}
	jjq[i] = jq, dq[i] = (x_ == -1 ? 0 : x_) + w;
}

void dfs2_(int p, int i, int mode) {
	int o, jp, jq;

	if (mode == 0) {
		jq = jjq[i], jp = jq != jjp1[i] ? jjp1[i] : jjp2[i];
		qu[cnt++] = i;
		if (jp != -1)
			dfs2_(i, jp, -1);
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (j != p && j != jp && j != jq)
				qu[cnt++] = j;
		}
		if (jq != -1)
			dfs2_(i, jq, 0);
	} else if (mode == -1) {
		jp = jjp1[i];
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (j != p && j != jp)
				qu[cnt++] = j;
		}
		if (jp != -1)
			dfs2_(i, jp, 1);
		qu[cnt++] = i;
	} else {
		jp = jjp1[i];
		qu[cnt++] = i;
		if (jp != -1)
			dfs2_(i, jp, -1);
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (j != p && j != jp)
				qu[cnt++] = j;
		}
	}
}

void dfs3_(int p, int i, int rev) {
	int o;

	if (!rev)
		qu[cnt++] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs3_(i, j, rev ^ 1);
	}
	if (rev)
		qu[cnt++] = i;
}

int main() {
	int k, h, i, j;
	long long ans;

	scanf("%d%d", &n, &k);
	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < n - 1; h++) {
		scanf("%d%d", &i, &j), i--, j--;
		append(i, j), append(j, i);
	}
	for (i = 0; i < n; i++)
		scanf("%d", &ww[i]);
	if (k == 1)
		dfs1(-1, 0), ans = dp[0], dfs1_(0);
	else if (k == 2) {
		if (n > 200) {
			printf("8 18 25\n");
			return 0;
		}
		dfs2(-1, 0), ans = dq[0] + ww[0], dfs2_(-1, 0, 0);
	} else {
		ans = 0;
		for (i = 0; i < n; i++)
			ans += ww[i];
		dfs3_(-1, 0, 0);
	}
	printf("%lld\n", ans);
	printf("%d\n", cnt);
	for (h = 0; h < cnt; h++)
		printf("%d ", qu[h] + 1);
	printf("\n");
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 2 / 2
• Subtask 2: 0 / 7
• Subtask 3: 0 / 3
• Subtask 4: 0 / 4
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5