Submission #993683

#	Time	Username	Problem	Language	Result	Execution time	Memory
993683		Trisanu_Das	Travelling Trader (CCO23_day2problem2)	C++17	25 / 25	177 ms	44216 KiB

Main

#include <stdio.h>
#include <stdlib.h>
 
#define N	200000
 
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], dr[N]; int jjp1[N], jjp2[N], jjp3[N], jjq[N], jjr[N]; char ttq[N], ttr[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;
		}
	}
	dp[i] = (j_ == -1 ? 0 : dp[j_]) + ww[i], jjp1[i] = j_;
}
 
void dfs1_(int i) {
	qu[cnt++] = i;
	if (jjp1[i] != -1)
		dfs1_(jjp1[i]);
}
 
void dfs2(int p, int i) {
	int o, jp1, jp2, jp3, jp1_, jp2_, jq, jr, t;
	long long w, x, x_;
 
	w = 0, jp1 = jp2 = jp3 = -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])
				jp3 = jp2, jp2 = jp1, jp1 = j;
			else if (jp2 == -1 || dp[jp2] < dp[j])
				jp3 = jp2, jp2 = j;
			else if (jp3 == -1 || dp[jp3] < dp[j])
				jp3 = j;
		}
	}
	dp[i] = (jp1 == -1 ? 0 : dp[jp1]) + w, jjp1[i] = jp1, jjp2[i] = jp2, jjp3[i] = jp3;
	x_ = -1, jq = -1, t = 2;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];
 
		if (j != p) {
			jp1_ = j != jp1 ? jp1 : jp2;
			x = (jp1_ == -1 ? 0 : dp[jp1_]) + dq[j] + w;
			if (x_ < x)
				x_ = x, jq = j, t = 2;
			x = dr[j] + ww[j];
			if (x_ < x)
				x_ = x, jq = j, t = 3;
		}
	}
	dq[i] = x_ == -1 ? 0 : x_, jjq[i] = jq, ttq[i] = t;
	x_ = -1, jr = -1, t = 2;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];
 
		if (j != p) {
			if (j == jp1)
				jp1_ = jp2, jp2_ = jp3;
			else if (j == jp2)
				jp1_ = jp1, jp2_ = jp3;
			else
				jp1_ = jp1, jp2_ = jp2;
			x = (jp1_ == -1 ? 0 : dp[jp1_]) + (jp2_ == -1 ? 0 : dp[jp2_]) + dq[j] + w;
			if (x_ < x)
				x_ = x, jr = j, t = 2;
			x = (jp1_ == -1 ? 0 : dp[jp1_]) + dr[j] + w;
			if (x_ < x)
				x_ = x, jr = j, t = 3;
		}
	}
	dr[i] = x_ == -1 ? 0 : x_, jjr[i] = jr, ttr[i] = t;
}
 
void dfs2_(int p, int i, int mode) {
	int o, jp1, jp2, jq, jr;
 
	if (mode == -1) {
		jp1 = jjp1[i];
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];
 
			if (j != p && j != jp1)
				qu[cnt++] = j;
		}
		if (jp1 != -1)
			dfs2_(i, jp1, 1);
		qu[cnt++] = i;
	} else if (mode == 1) {
		jp1 = jjp1[i];
		qu[cnt++] = i;
		if (jp1 != -1)
			dfs2_(i, jp1, -1);
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];
 
			if (j != p && j != jp1)
				qu[cnt++] = j;
		}
	} else if (mode == 2) {
		jq = jjq[i], jp1 = jq != jjp1[i] ? jjp1[i] : jjp2[i];
		if (ttq[i] == 2) {
			qu[cnt++] = i;
			if (jp1 != -1)
				dfs2_(i, jp1, -1);
			for (o = eo[i]; o--; ) {
				int j = ej[i][o];
 
				if (j != p && j != jp1 && j != jq)
					qu[cnt++] = j;
			}
			if (jq != -1)
				dfs2_(i, jq, 2);
		} else {
			qu[cnt++] = i;
			dfs2_(i, jq, 3);
		}
	} else {
		jr = jjr[i];
		if (jr == jjp1[i])
			jp1 = jjp2[i], jp2 = jjp3[i];
		else if (jr == jjp2[i])
			jp1 = jjp1[i], jp2 = jjp3[i];
		else
			jp1 = jjp1[i], jp2 = jjp2[i];
		if (ttr[i] == 2) {
			if (jp1 != -1)
				dfs2_(i, jp1, 1);
			qu[cnt++] = i;
			if (jp2 != -1)
				dfs2_(i, jp2, -1);
			for (o = eo[i]; o--; ) {
				int j = ej[i][o];
 
				if (j != p && j != jp1 && j != jp2 && j != jr)
					qu[cnt++] = j;
			}
			if (jr != -1)
				dfs2_(i, jr, 2);
		} else {
			for (o = eo[i]; o--; ) {
				int j = ej[i][o];
 
				if (j != p && j != jp1 && j != jr)
					qu[cnt++] = j;
			}
			if (jp1 != -1)
				dfs2_(i, jp1, 1);
			qu[cnt++] = i;
			dfs2_(i, jr, 3);
		}
	}
}
 
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)
		dfs2(-1, 0), ans = dq[0] + ww[0], dfs2_(-1, 0, 2);
	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.cpp: In function 'void append(int, int)':
Main.cpp:11:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   11 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~
Main.cpp: In function 'int main()':
Main.cpp:197:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |  scanf("%d%d", &n, &k);
      |  ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:201:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  201 |   scanf("%d%d", &i, &j), i--, j--;
      |   ~~~~~^~~~~~~~~~~~~~~~
Main.cpp:205:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  205 |   scanf("%d", &ww[i]);
      |   ~~~~~^~~~~~~~~~~~~~

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