oj.uz

Submission #882968

# Submission time Handle Problem Language Result Execution time Memory
882968 2023-12-04T09:36:19 Z tsumondai Travelling Trader (CCO23_day2problem2) C++14
25 / 25
 304 ms 132392 KB 
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<int, ii> iii;
typedef pair<ii, ii> iiii;

const int N = 1e6 + 5;

const int oo = 1e18, mod = 1e9 + 7;

int n, m, k, a[N];
vector<int> edges[N];


namespace subtask1 {
ii dist[N];
void dfs(int u, int par) {
	dist[u] = {0, u};
	for (int v : edges[u]) {
		if (v == par) continue;
		dfs(v, u);
		dist[u] = max(dist[u], {dist[v].fi, v});
	}
	dist[u].fi += a[u];
}
void process() {
	dfs(1, 0);
	cout << dist[1].fi << '\n';
	vector<int> res;
	int u = 1; res.push_back(u);
	while (dist[u].se != u) {
		u = dist[u].se;
		res.push_back(u);
	}
	cout << (int)res.size() << '\n';
	for (int v : res) cout << v << (v == res.back() ? '\n' : ' ');
}
}
namespace subtask2 {
int dp[N][2][2];
iii trace[N][2][2];
vector<int> res;

void dfs(int u, int par) {
	int total = 0;
	for (int v : edges[u]) {
		if (v == par) continue;
		dfs(v, u); total += a[v];
	}
	{	//cur = u and jump back to par
		ii Max = {0, 0};
		for (int v : edges[u]) {
			if (v == par) continue;
			Max = max(Max, {dp[v][1][1] + total, v});
		}
		dp[u][0][1] = Max.fi;
		trace[u][0][1] = {Max.se, {0, 0}};
	}
	{	//cur = child of u and jump back to u
		ii Max = {0, 0};
		for (int v : edges[u]) {
			if (v == par) continue;
			Max = max(Max, {dp[v][0][1] + total, v});
		}
		dp[u][1][1] = Max.fi;
		trace[u][1][1] = {Max.se, {0, 0}};
	}
	{	//cur = u and not jump back
		iii Max = {0, {0, 0}};
		vector<ii> p1 = {{0, 0}}, p2 = {{0, 0}};
		for (int v : edges[u]) {
			if (v == par) continue;
			Max = max(Max, {dp[v][1][0] + a[v], { -1, v}});
			p1.push_back({dp[v][1][1], v});
			p2.push_back({dp[v][0][0], v});
		}
		sort(p1.begin(), p1.end(), greater<ii>());
		sort(p2.begin(), p2.end(), greater<ii>());
		for (int i = 0; i < min(2LL, (int)p1.size()); i++)
			for (int j = 0; j < min(2LL, (int)p2.size()); j++) {
				if (p2[j].se != 0 && p2[j].se == p1[i].se) continue;
				Max = max(Max, {p1[i].fi + p2[j].fi + total, {p1[i].se, p2[j].se}});
			}
		dp[u][0][0] = Max.fi;
		trace[u][0][0] = {Max.se.fi, {Max.se.se, 0}};
	}
	{	//cur = child of u and not jump back
		pair<int, iii> Max = {0, {0, {0, 0}}};
		{
			iii Max2 = {0, {0, 0}};
			vector<ii> p1 = {{0, 0}}, p2 = {{0, 0}};
			for (int v : edges[u]) {
				if (v == par) continue;
				p1.push_back({dp[v][0][1], v});
				p2.push_back({dp[v][1][0], v});
			}
			sort(p1.begin(), p1.end(), greater<ii>());
			sort(p2.begin(), p2.end(), greater<ii>());
			for (int i = 0; i < min(2LL, (int)p1.size()); i++)
				for (int j = 0; j < min(2LL, (int)p2.size()); j++) {
					if (p2[j].se != 0 && p2[j].se == p1[i].se) continue;
					Max2 = max(Max2, {p1[i].fi + p2[j].fi + total, {p1[i].se, p2[j].se}});
				}
			Max = max(Max, {Max2.fi, { -1, Max2.se}});
		}

		vector<ii> p1 = {{0, 0}}, p2 = {{0, 0}}, p3 = {{0, 0}};
		for (int v : edges[u]) {
			if (v == par) continue;
			p1.push_back({dp[v][0][1], v});
			p2.push_back({dp[v][1][1], v});
			p3.push_back({dp[v][0][0], v});
		}
		sort(p1.begin(), p1.end(), greater<ii>());
		sort(p2.begin(), p2.end(), greater<ii>());
		sort(p3.begin(), p3.end(), greater<ii>());
		for (int i = 0; i < min(3LL, (int)p1.size()); i++)
			for (int j = 0; j < min(3LL, (int)p2.size()); j++)
				for (int k = 0; k < min(3LL, (int)p3.size()); k++) {
					if (p2[j].se != 0 && p2[j].se == p1[i].se) continue;
					if (p3[k].se != 0 && (p3[k].se == p1[i].se || p3[k].se == p2[j].se)) continue;
					Max = max(Max, {p1[i].fi + p2[j].fi + p3[k].fi + total, {p1[i].se, {p2[j].se, p3[k].se}}});
				}
		dp[u][1][0] = Max.fi;
		trace[u][1][0] = Max.se;
	}
}

void f(int u, int par, int t1, int t2) {
	if (!t1 && t2) {
		res.push_back(u);
		if (trace[u][0][1].fi) f(trace[u][0][1].fi, u, 1, 1);
		for (int v : edges[u]) {
			if (v == par) continue;
			if (v == trace[u][0][1].fi) continue;
			res.push_back(v);
		}
	}
	else if (t1 && t2) {
		for (int v : edges[u]) {
			if (v == par) continue;
			if (v == trace[u][1][1].fi) continue;
			res.push_back(v);
		}
		if (trace[u][1][1].fi) f(trace[u][1][1].fi, u, 0, 1);
		res.push_back(u);
	}
	else if (!t1 && !t2) {
		res.push_back(u);
		if (trace[u][0][0].fi == -1) {
			if (trace[u][0][0].se.fi) f(trace[u][0][0].se.fi, u, 1, 0);
			return;
		}
		if (trace[u][0][0].fi) f(trace[u][0][0].fi, u, 1, 1);
		for (int v : edges[u]) {
			if (v == par) continue;
			if (v == trace[u][0][0].se.fi || v == trace[u][0][0].fi) continue;
			res.push_back(v);
		}
		if (trace[u][0][0].se.fi) f(trace[u][0][0].se.fi, u, 0, 0);
	}
	else {
		if (trace[u][1][0].fi == -1) {
			for (int v : edges[u]) {
				if (v == par) continue;
				if (v == trace[u][1][0].se.fi || v == trace[u][1][0].se.se) continue;
				res.push_back(v);
			}
			if (trace[u][1][0].se.fi) f(trace[u][1][0].se.fi, u, 0, 1);
			res.push_back(u);
			if (trace[u][1][0].se.se) f(trace[u][1][0].se.se, u, 1, 0);
			return;
		}
		if (trace[u][1][0].fi) f(trace[u][1][0].fi, u, 0, 1);
		res.push_back(u);
		if (trace[u][1][0].se.fi) f(trace[u][1][0].se.fi, u, 1, 1);
		for (int v : edges[u]) {
			if (v == par) continue;
			if (v == trace[u][1][0].fi || v == trace[u][1][0].se.fi || v == trace[u][1][0].se.se) continue;
			res.push_back(v);
		}
		if (trace[u][1][0].se.se) f(trace[u][1][0].se.se, u, 0, 0);
	}
}

void process() {
	dfs(1, 0);
	f(1, 0, 0, 0);
	cout << dp[1][0][0] + a[1] << '\n';
	cout << (int)res.size() << '\n';
	for (int v : res) cout << v << (v == res.back() ? '\n' : ' ');
}
}

namespace subtask3 {

vector<int> res;
void dfs(int u, int par) {
	res.push_back(u);
	for (int v : edges[u]) {
		if (v == par) continue;
		for (int w : edges[v]) {
			if (w == u) continue;
			dfs(w, v);
		}
		res.push_back(v);
	}
}

void process() {
	int total = 0;
	for (int i = 1; i <= n; i++) total += a[i];
	dfs(1, 0);
	cout << total << '\n';
	cout << n << '\n';
	for (int v : res) cout << v << (v == res.back() ? '\n' : ' ');
}

}

signed main() {
	cin.tie(0)->sync_with_stdio(false);
	//freopen(".inp", "r", stdin);
	//freopen(".out", "w", stdout);
	cin >> n >> k;
	foru(i, 1, n - 1) {
		int u, v; cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}
	foru(i, 1, n) cin >> a[i];
	if (k == 1) subtask1::process();
	if (k == 2) subtask2::process();
	if (k == 3) subtask3::process();
	cerr << "Time elapsed: " << __TIME << " s.\n";
	return 0;
}

// dont stop

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 99 ms 44112 KB Output is correct
4 Correct 98 ms 45228 KB Output is correct
5 Correct 98 ms 44884 KB Output is correct
6 Correct 90 ms 45908 KB Output is correct
7 Correct 69 ms 44680 KB Output is correct
8 Correct 83 ms 44228 KB Output is correct
9 Correct 145 ms 68912 KB Output is correct
10 Correct 158 ms 58644 KB Output is correct
11 Correct 63 ms 45248 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct

Subtask #2
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29124 KB Output is correct
8 Correct 7 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 6 ms 29020 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct
13 Correct 7 ms 29152 KB Output is correct
14 Correct 6 ms 29020 KB Output is correct
15 Correct 6 ms 29020 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 6 ms 29020 KB Output is correct
18 Correct 7 ms 29020 KB Output is correct
19 Correct 6 ms 29144 KB Output is correct
20 Correct 6 ms 29184 KB Output is correct
21 Correct 6 ms 29020 KB Output is correct
22 Correct 6 ms 29092 KB Output is correct
23 Correct 6 ms 29020 KB Output is correct
24 Correct 6 ms 29020 KB Output is correct
25 Correct 6 ms 29020 KB Output is correct
26 Correct 6 ms 29020 KB Output is correct
27 Correct 6 ms 29020 KB Output is correct
28 Correct 6 ms 29020 KB Output is correct

Subtask #3
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29124 KB Output is correct
8 Correct 7 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 6 ms 29020 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct
13 Correct 7 ms 29152 KB Output is correct
14 Correct 6 ms 29020 KB Output is correct
15 Correct 6 ms 29020 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 6 ms 29020 KB Output is correct
18 Correct 7 ms 29020 KB Output is correct
19 Correct 6 ms 29144 KB Output is correct
20 Correct 6 ms 29184 KB Output is correct
21 Correct 6 ms 29020 KB Output is correct
22 Correct 6 ms 29092 KB Output is correct
23 Correct 6 ms 29020 KB Output is correct
24 Correct 6 ms 29020 KB Output is correct
25 Correct 6 ms 29020 KB Output is correct
26 Correct 6 ms 29020 KB Output is correct
27 Correct 6 ms 29020 KB Output is correct
28 Correct 6 ms 29020 KB Output is correct
29 Correct 9 ms 31324 KB Output is correct
30 Correct 8 ms 31324 KB Output is correct
31 Correct 8 ms 31324 KB Output is correct
32 Correct 8 ms 31324 KB Output is correct
33 Correct 8 ms 31324 KB Output is correct
34 Correct 8 ms 31324 KB Output is correct
35 Correct 8 ms 31324 KB Output is correct
36 Correct 8 ms 31324 KB Output is correct
37 Correct 8 ms 31324 KB Output is correct
38 Correct 9 ms 31664 KB Output is correct
39 Correct 8 ms 31580 KB Output is correct
40 Correct 7 ms 31324 KB Output is correct
41 Correct 8 ms 31440 KB Output is correct
42 Correct 8 ms 32092 KB Output is correct
43 Correct 8 ms 32088 KB Output is correct
44 Correct 8 ms 31504 KB Output is correct
45 Correct 8 ms 31580 KB Output is correct
46 Correct 8 ms 31612 KB Output is correct
47 Correct 8 ms 31580 KB Output is correct
48 Correct 7 ms 31324 KB Output is correct
49 Correct 7 ms 31328 KB Output is correct

Subtask #4
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 29020 KB Output is correct
2 Correct 6 ms 29020 KB Output is correct
3 Correct 6 ms 29020 KB Output is correct
4 Correct 6 ms 29276 KB Output is correct
5 Correct 6 ms 29020 KB Output is correct
6 Correct 6 ms 29020 KB Output is correct
7 Correct 6 ms 29124 KB Output is correct
8 Correct 7 ms 29020 KB Output is correct
9 Correct 6 ms 29020 KB Output is correct
10 Correct 6 ms 29020 KB Output is correct
11 Correct 6 ms 29020 KB Output is correct
12 Correct 6 ms 29020 KB Output is correct
13 Correct 7 ms 29152 KB Output is correct
14 Correct 6 ms 29020 KB Output is correct
15 Correct 6 ms 29020 KB Output is correct
16 Correct 6 ms 29020 KB Output is correct
17 Correct 6 ms 29020 KB Output is correct
18 Correct 7 ms 29020 KB Output is correct
19 Correct 6 ms 29144 KB Output is correct
20 Correct 6 ms 29184 KB Output is correct
21 Correct 6 ms 29020 KB Output is correct
22 Correct 6 ms 29092 KB Output is correct
23 Correct 6 ms 29020 KB Output is correct
24 Correct 6 ms 29020 KB Output is correct
25 Correct 6 ms 29020 KB Output is correct
26 Correct 6 ms 29020 KB Output is correct
27 Correct 6 ms 29020 KB Output is correct
28 Correct 6 ms 29020 KB Output is correct
29 Correct 9 ms 31324 KB Output is correct
30 Correct 8 ms 31324 KB Output is correct
31 Correct 8 ms 31324 KB Output is correct
32 Correct 8 ms 31324 KB Output is correct
33 Correct 8 ms 31324 KB Output is correct
34 Correct 8 ms 31324 KB Output is correct
35 Correct 8 ms 31324 KB Output is correct
36 Correct 8 ms 31324 KB Output is correct
37 Correct 8 ms 31324 KB Output is correct
38 Correct 9 ms 31664 KB Output is correct
39 Correct 8 ms 31580 KB Output is correct
40 Correct 7 ms 31324 KB Output is correct
41 Correct 8 ms 31440 KB Output is correct
42 Correct 8 ms 32092 KB Output is correct
43 Correct 8 ms 32088 KB Output is correct
44 Correct 8 ms 31504 KB Output is correct
45 Correct 8 ms 31580 KB Output is correct
46 Correct 8 ms 31612 KB Output is correct
47 Correct 8 ms 31580 KB Output is correct
48 Correct 7 ms 31324 KB Output is correct
49 Correct 7 ms 31328 KB Output is correct
50 Correct 241 ms 67980 KB Output is correct
51 Correct 230 ms 67976 KB Output is correct
52 Correct 222 ms 67968 KB Output is correct
53 Correct 224 ms 68160 KB Output is correct
54 Correct 209 ms 67924 KB Output is correct
55 Correct 246 ms 68068 KB Output is correct
56 Correct 195 ms 68692 KB Output is correct
57 Correct 220 ms 67924 KB Output is correct
58 Correct 192 ms 68640 KB Output is correct
59 Correct 226 ms 67924 KB Output is correct
60 Correct 204 ms 68852 KB Output is correct
61 Correct 273 ms 82588 KB Output is correct
62 Correct 255 ms 74176 KB Output is correct
63 Correct 222 ms 71292 KB Output is correct
64 Correct 212 ms 68476 KB Output is correct
65 Correct 304 ms 132392 KB Output is correct
66 Correct 295 ms 103340 KB Output is correct
67 Correct 253 ms 88520 KB Output is correct
68 Correct 254 ms 87656 KB Output is correct
69 Correct 260 ms 79064 KB Output is correct
70 Correct 229 ms 76324 KB Output is correct
71 Correct 150 ms 68180 KB Output is correct
72 Correct 136 ms 67568 KB Output is correct

Subtask #5
4.0 / 4.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 7 ms 27328 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 7 ms 27384 KB Output is correct
5 Correct 6 ms 27480 KB Output is correct
6 Correct 8 ms 27228 KB Output is correct
7 Correct 6 ms 26972 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 7 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27076 KB Output is correct
13 Correct 7 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 6 ms 27228 KB Output is correct
16 Correct 6 ms 27228 KB Output is correct
17 Correct 6 ms 27148 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 6 ms 27228 KB Output is correct
20 Correct 7 ms 27228 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 7 ms 27152 KB Output is correct
23 Correct 7 ms 27320 KB Output is correct

Subtask #6
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 27228 KB Output is correct
2 Correct 7 ms 27328 KB Output is correct
3 Correct 8 ms 27228 KB Output is correct
4 Correct 7 ms 27384 KB Output is correct
5 Correct 6 ms 27480 KB Output is correct
6 Correct 8 ms 27228 KB Output is correct
7 Correct 6 ms 26972 KB Output is correct
8 Correct 6 ms 26972 KB Output is correct
9 Correct 6 ms 27228 KB Output is correct
10 Correct 7 ms 27228 KB Output is correct
11 Correct 6 ms 27228 KB Output is correct
12 Correct 6 ms 27076 KB Output is correct
13 Correct 7 ms 27228 KB Output is correct
14 Correct 6 ms 27228 KB Output is correct
15 Correct 6 ms 27228 KB Output is correct
16 Correct 6 ms 27228 KB Output is correct
17 Correct 6 ms 27148 KB Output is correct
18 Correct 6 ms 27228 KB Output is correct
19 Correct 6 ms 27228 KB Output is correct
20 Correct 7 ms 27228 KB Output is correct
21 Correct 6 ms 27228 KB Output is correct
22 Correct 7 ms 27152 KB Output is correct
23 Correct 7 ms 27320 KB Output is correct
24 Correct 116 ms 41844 KB Output is correct
25 Correct 108 ms 41964 KB Output is correct
26 Correct 101 ms 41924 KB Output is correct
27 Correct 102 ms 41972 KB Output is correct
28 Correct 110 ms 41852 KB Output is correct
29 Correct 107 ms 41668 KB Output is correct
30 Correct 107 ms 42804 KB Output is correct
31 Correct 102 ms 41868 KB Output is correct
32 Correct 103 ms 42692 KB Output is correct
33 Correct 132 ms 42052 KB Output is correct
34 Correct 93 ms 42940 KB Output is correct
35 Correct 78 ms 41532 KB Output is correct
36 Correct 92 ms 41024 KB Output is correct
37 Correct 103 ms 41792 KB Output is correct
38 Correct 92 ms 42428 KB Output is correct
39 Correct 124 ms 50488 KB Output is correct
40 Correct 123 ms 47756 KB Output is correct
41 Correct 111 ms 46100 KB Output is correct
42 Correct 116 ms 45444 KB Output is correct
43 Correct 110 ms 44232 KB Output is correct
44 Correct 117 ms 43044 KB Output is correct
45 Correct 77 ms 42160 KB Output is correct
46 Correct 75 ms 41672 KB Output is correct