QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#117957#6629. Travelling Tradervalerikk#0 4ms12416kbC++172.9kb2023-07-02 17:56:162024-05-31 18:47:26

Judging History

你现在查看的是最新测评结果

  • [2024-05-31 18:47:26]
  • 评测
  • 测评结果:0
  • 用时:4ms
  • 内存:12416kb
  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-02 17:56:16]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 2e5 + 7;
const ll INF = 2e18;

int n, k;
vector<int> g[N];
int a[N];
ll dp[N], dpret[N];

void dfs(int v, int p = -1) {
	if (p != -1) {
		g[v].erase(find(g[v].begin(), g[v].end(), p));
	}
	for (int u : g[v]) {
		dfs(u, v);
	}
	ll sum = 0;
	for (int u : g[v]) {
		sum += a[u];
	}
	{
		dp[v] = a[v];
		for (int u : g[v]) {
			dp[v] = max(dp[v], a[v] + dp[u] - a[u] + sum);
			dp[v] = max(dp[v], a[v] + dpret[u] - a[u] + sum);
		}
		for (int u : g[v]) {
			for (int w : g[v]) {
				if (u != w) {
					dp[v] = max(dp[v], a[v] + dp[u] - a[u] + dpret[w] - a[w] + sum);
				}
			}
		}
	}
	{
		dpret[v] = a[v] + sum;
		for (int u : g[v]) {
			dpret[v] = max(dpret[v], a[v] + dpret[u] - a[u] + sum);
		}
	}
}

vector<int> getordret(int v) {
	ll sum = 0;
	for (int u : g[v]) {
		sum += a[u];
	}
	if (dpret[v] == a[v] + sum) {
		vector<int> ord = {v};
		for (int u : g[v]) {
			ord.push_back(u);
		}
		return ord;
	}
	for (int u : g[v]) {
		if (dpret[v] == a[v] + dpret[u] - a[u] + sum) {
			vector<int> ord = {v};
			auto ordu = getordret(u);
			reverse(ordu.begin(), ordu.end());
			for (int w : ordu) {
				ord.push_back(w);
			}
			for (int w : g[v]) {
				if (w != u) {
					ord.push_back(w);
				}
			}
			return ord;
		}
	}
	assert(0);
	return {v};
}

vector<int> getord(int v) {
	ll sum = 0;
	for (int u : g[v]) {
		sum += a[u];
	}
	if (dp[v] == a[v]) {
		return {v};
	}
	for (int u : g[v]) {
		if (dp[v] == a[v] + dp[u] - a[u] + sum) {
			vector<int> ord = {v};
			for (int w : g[v]) {
				if (w != u) {
					ord.push_back(w);
				}
			}
			auto ordu = getord(u);
			for (int w : ordu) {
				ord.push_back(w);
			}
			return ord;
		}
		if (dp[v] == a[v] + dpret[u] - a[u] + sum) {
			vector<int> ord = {v};
			auto ordu = getordret(u);
			reverse(ordu.begin(), ordu.end());
			for (int w : ordu) {
				ord.push_back(w);
			}
			for (int w : g[v]) {
				if (w != u) {
					ord.push_back(w);
				}
			}
			return ord;
		}
		for (int w : g[v]) {
			if (dp[v] == a[v] + dp[u] - a[u] + dpret[w] - a[w] + sum) {
				vector<int> ord = {v};
				auto ordu = getord(u);
				auto ordw = getordret(w);
				reverse(ordw.begin(), ordw.end());
				for (int l : ordw) {
					ord.push_back(l);
				}
				for (int l : g[v]) {
					if (l != u && l != w) {
						ord.push_back(l);
					}
				}
				for (int l : ordu) {
					ord.push_back(l);
				}
				return ord;
			}
		}
	}
	assert(0);
	return {v};
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> n >> k;
	for (int i = 0; i < n - 1; ++i) {
		int v, u;
		cin >> v >> u;
		--v, --u;
		g[v].push_back(u);
		g[u].push_back(v);
	}
	for (int i = 0; i < n; ++i) {
		cin >> a[i];
	}
	dfs(0);
	ll ans = max(dp[0], dpret[0]);
	vector<int> ord;
	if (ans == dp[0]) {
		ord = getord(0);
	} else {
		ord = getordret(0);
	}
	cout << ans << "\n";
	cout << ord.size() << "\n";
	for (int v : ord) {
		cout << v + 1 << " ";
	}
	cout << "\n";
	return 0;	
}

Details

Tip: Click on the bar to expand more detailed information

Subtask #1:

score: 0
Wrong Answer

Test #1:

score: 2
Accepted
time: 0ms
memory: 11392kb

input:

2 1
1 2
255959470 961356354

output:

1217315824
2
1 2 

result:

ok correct!

Test #2:

score: -2
Wrong Answer
time: 2ms
memory: 12056kb

input:

1000 1
730 89
762 280
923 523
740 22
679 350
448 769
102 712
154 965
219 32
238 289
484 502
183 311
999 682
806 450
275 101
131 197
749 720
131 937
960 202
503 320
95 262
595 133
809 560
659 451
843 218
258 842
564 316
729 727
413 237
606 531
469 258
612 8
707 539
359 680
957 639
381 708
104 490
234...

output:

1370702
268
1 929 264 819 173 273 641 858 902 391 704 961 418 471 392 642 728 654 283 656 511 449 548 622 542 169 368 896 694 472 605 685 393 691 921 540 505 470 185 874 103 778 824 89 69 437 358 202 747 396 750 222 144 42 106 467 569 193 975 13 551 289 344 518 959 587 114 857 803 731 768 108 238 81...

result:

wrong answer dist(1, 929) = 2 > k = 1

Subtask #2:

score: 0
Wrong Answer

Test #12:

score: 7
Accepted
time: 2ms
memory: 10376kb

input:

2 2
2 1
243296356 635616793

output:

878913149
2
1 2 

result:

ok correct!

Test #13:

score: 0
Accepted
time: 2ms
memory: 11848kb

input:

10 2
6 4
3 7
5 10
6 10
8 2
3 9
3 5
4 2
1 4
2 4 2 5 5 4 2 3 4 2

output:

33
10
1 4 8 2 6 10 5 3 9 7 

result:

ok correct!

Test #14:

score: -7
Wrong Answer
time: 0ms
memory: 11540kb

input:

200 2
150 170
21 33
96 152
143 26
136 70
92 159
34 164
163 182
74 115
93 61
151 83
81 119
10 146
114 170
39 83
139 4
173 41
193 96
87 57
14 164
107 51
45 15
157 17
43 183
96 30
11 137
55 18
138 81
87 12
112 122
159 82
195 185
75 71
16 191
33 88
70 195
149 114
106 160
96 118
92 44
9 141
107 143
151 2...

output:

54153356810
91
1 151 179 194 89 83 135 27 122 117 120 180 125 112 40 45 138 94 162 88 21 193 59 170 149 110 28 171 114 96 105 131 33 15 99 72 12 76 70 53 159 17 178 24 44 41 67 173 186 42 116 92 82 197 101 5 32 121 87 29 198 64 93 19 126 8 141 37 100 3 9 108 52 61 54 14 137 49 26 165 47 50 148 75 12...

result:

wrong answer your profit is 54153356810 but jury's plan is 57921623677, your plan is not optimal!

Subtask #3:

score: 0
Skipped

Dependency #2:

0%

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Wrong Answer

Test #83:

score: 4
Accepted
time: 3ms
memory: 12416kb

input:

2000 3
1359 90
1703 163
158 188
360 1501
195 664
1414 215
1546 1756
536 1096
1726 1223
1150 104
1757 703
1982 282
1023 998
1180 419
576 1759
1496 1993
44 670
1703 952
855 849
1998 1399
1280 980
1533 1090
1270 678
1680 387
469 1734
1799 263
473 588
303 226
5 295
1489 1471
1094 1667
1912 210
1368 1360...

output:

1008611451196
2000
1 1091 961 605 1613 454 1237 1823 1101 1617 1369 1840 562 1256 901 1040 709 1291 1238 1526 129 523 816 1919 674 1961 452 297 1903 1656 560 739 183 1522 951 863 877 1973 1548 191 1265 1344 33 1679 565 774 276 139 926 1397 46 36 1019 1427 289 1376 545 16 1880 1076 1684 1968 1504 81 ...

result:

ok correct!

Test #84:

score: 0
Accepted
time: 4ms
memory: 11508kb

input:

2000 3
1727 567
1783 1850
205 985
323 1094
1153 821
1756 117
377 1928
1026 1303
1343 1814
268 745
242 948
1140 1218
7 1675
101 1798
1403 1752
1184 671
87 248
1953 30
1580 1441
507 1438
525 419
901 421
1585 1405
1575 883
1952 1930
1988 1325
615 722
994 1202
178 474
1978 1500
899 481
216 409
999 1817
...

output:

1012330476243
2000
1 369 1789 598 488 422 419 525 269 202 1079 694 1379 1724 1454 1545 88 1123 246 701 1522 1158 1696 1364 1918 131 1589 1832 872 1532 1057 345 1725 67 761 1634 1174 719 1807 650 693 61 718 554 841 1935 234 175 220 105 917 1784 997 1315 1530 92 257 1071 802 1369 1257 1046 1275 993 31...

result:

ok correct!

Test #85:

score: -4
Wrong Answer
time: 3ms
memory: 11444kb

input:

2000 3
1213 130
101 508
72 1199
1550 1096
1099 861
1515 627
1299 1672
1338 105
1444 1019
15 1560
1949 971
52 1312
30 529
186 1687
1917 484
1971 349
537 1223
1955 1377
300 1060
1786 1811
1960 90
1959 1353
1831 1548
303 511
1073 1197
863 1527
1379 994
31 9
1247 1707
1395 1532
29 1544
119 296
1919 1554...

output:

803960409885
1502
1 1365 1487 810 1721 1986 1821 668 513 830 1002 1255 1557 751 574 1658 1802 1491 60 1261 640 374 1010 1292 1450 1710 1896 718 942 1246 706 295 1377 1955 729 954 242 1809 93 1610 381 435 1127 863 384 1356 1067 181 1503 1169 1153 1241 1997 563 1475 1303 1310 1208 388 1069 1483 1181 8...

result:

wrong answer your profit is 803960409885 but jury's plan is 1001405462082, your plan is not optimal!

Subtask #6:

score: 0
Skipped

Dependency #5:

0%