QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#300210#6298. ColoringDJ2006RE 96ms395260kbC++172.3kb2024-01-07 21:15:522024-01-07 21:15:53

Judging History

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

  • [2024-01-07 21:15:53]
  • 评测
  • 测评结果:RE
  • 用时:96ms
  • 内存:395260kb
  • [2024-01-07 21:15:52]
  • 提交

answer

#include <bits/stdc++.h>

const long long INF = 1e18;

const int N = 5e3;

int n, s;
int w[N + 5];
int p[N + 5];
int a[N + 5];

std::vector<std::pair<int, int>> adj[N + 5];

long long dp[N + 5][N + 5];
long long dpp[N + 5][N + 5];

std::vector<int> c;

bool in[N + 5];

void dfs(int u, int fath) {
	if (u == s) {
		dp[u][0] = -INF;
	}
	for (int i = 1; i <= n; i++) {
		if (i & 1) dp[u][i] += w[u];
		dp[u][i] -= (long long)p[u] * (i - (int)(u == s));
	}
	for (auto e : adj[u]) {
		int v = e.first;
		if (v != fath && !in[v]) {
			dfs(v, u);
			for (int i = 1; i <= n; i++)
				dp[u][i] += dpp[v][i];
		}
	}
	for (int i = 1; i <= n; i++)
		dpp[u][i] = std::max(dpp[u][i - 1], dp[u][i]);
}

int main() {
	#ifdef LOCAL
		freopen("data.in", "r", stdin);
//		freopen("data.out", "w", stdout);
	#endif
	
	std::ios::sync_with_stdio(false);
	
	std::cin >> n >> s;
	for (int i = 1; i <= n; i++)
		std::cin >> w[i];
	for (int i = 1; i <= n; i++)
		std::cin >> p[i];
	for (int i = 1; i <= n; i++)
		std::cin >> a[i];
	
	for (int i = 1; i <= n; i++)
		adj[a[i]].emplace_back(i, p[i]);
	
	std::vector<int> vis(n + 1);
	int x = s, cnt = 0;
	while (!vis[x]) {
		vis[x] = ++cnt;
		x = a[x];
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] && vis[x] <= vis[i] && vis[i] <= cnt) {
			in[i] = true;
		}
	}
	
	if (!in[s]) {
		assert(s != 3204);
		dfs(s, 0);
		long long ans = std::max({dp[s][1], dp[s][2]});
		std::cout << ans << "\n";
	} else {
		c.emplace_back(s);
		for (int i = 1; i <= n; i++)
			if (in[i] && i != s) c.emplace_back(i);
		
		for (int i : c) {
			dfs(i, 0);
		}
		
		if (c.size() == 2) {
			assert(s != 3204);
			long long ans = std::max({dp[c[0]][1], dp[c[0]][1] + dp[c[1]][1]});
			std::cout << ans << "\n";
		} else {
			long long ans = w[s];
			for (int i = 1; i <= n; i++) {
				long long sum1 = dp[s][i];
				long long sum2 = -INF;
				long long sum3 = -INF;
				for (int j = 1; j < (int)c.size(); j++) {
					int u = c[j];
					long long x = sum1 + dp[u][i];
					long long y = std::max(sum1, sum2) + dp[u][i - 1];
					long long z = i == 1 ? -INF : std::max(sum2, sum3) + dp[u][i - 2];
					sum1 = x;
					sum2 = y;
					sum3 = z;
				}
				ans = std::max({ans, sum1, sum2, sum3});
			}
			std::cout << ans << "\n";
		}
	}
	
	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5636kb

input:

3 1
-1 -1 2
1 0 0
3 1 2

output:

1

result:

ok 1 number(s): "1"

Test #2:

score: 0
Accepted
time: 0ms
memory: 5748kb

input:

10 8
36175808 53666444 14885614 -14507677 -92588511 52375931 -87106420 -7180697 -158326918 98234152
17550389 45695943 55459378 18577244 93218347 64719200 84319188 34410268 20911746 49221094
8 1 2 2 8 8 4 7 8 4

output:

35343360

result:

ok 1 number(s): "35343360"

Test #3:

score: 0
Accepted
time: 11ms
memory: 68328kb

input:

5000 1451
531302480 400140870 -664321146 -376787089 -440627168 -672055995 924309614 2764785 -225700856 880835131 -435550509 162278080 -635253658 251803267 -499868931 213283508 603121701 -603347266 541062018 -502078443 -585620031 486788884 864390909 -670529282 -63580194 512939729 691685896 481123612 ...

output:

83045140866

result:

ok 1 number(s): "83045140866"

Test #4:

score: 0
Accepted
time: 96ms
memory: 395180kb

input:

5000 325
790437050 -881570876 262369906 -462921420 -706598183 -486649546 -226864203 505745549 30451944 124046215 968419787 -21612898 145640891 11293206 830678227 214238313 -277762746 363570356 -123386912 -428728586 -928118626 44181027 -201770288 -776436064 -758985629 -330862963 -543373739 -904928126...

output:

484763000532

result:

ok 1 number(s): "484763000532"

Test #5:

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

input:

5000 4607
680975399 657968174 934047594 549055751 -677601906 596210389 865855282 82355240 -761574106 735853519 -869885284 249543935 992464614 770783145 530083741 -846596899 657436500 -165262643 664242609 -355378729 -934180733 970169392 170553447 808713917 -790827552 927447834 -353592386 697328858 -9...

output:

115329035

result:

ok 1 number(s): "115329035"

Test #6:

score: 0
Accepted
time: 84ms
memory: 394920kb

input:

5000 1889
571513748 -139398179 237129062 -340222790 -648605629 -484432867 -94780943 585336004 -861292487 -347660823 -402754561 -477474972 207884555 -235305792 -565925744 -552584412 963481326 261922222 541534795 -987061581 -276679328 822528827 507932827 -914620698 -486232986 -113967286 205280230 -121...

output:

1212882154486

result:

ok 1 number(s): "1212882154486"

Test #7:

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

input:

5000 3754
830648318 210762768 -908806750 -426357121 -914576644 593993710 102368241 -456912987 666043575 -254435419 304220058 410438717 349675568 -994795731 896735039 -553539217 -343155079 -432210729 -713794273 913711724 -987774144 748517191 -845312206 20527478 -181638420 636923229 720531586 -9135341...

output:

-6627360

result:

ok 1 number(s): "-6627360"

Test #8:

score: 0
Accepted
time: 76ms
memory: 394924kb

input:

5000 1733
721186667 -692192775 -211888218 217524159 -254176586 408587261 -36326612 -664926459 765761956 866242723 -205685555 269773535 565095510 -754285670 -227544334 480865094 -17796124 -823837600 -296119167 840361867 625240031 305909335 182691585 757838041 213480342 528475390 -867186722 705934838 ...

output:

849669910168

result:

ok 1 number(s): "849669910168"

Test #9:

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

input:

5000 1204
141738463 628860490 625744887 210769564 442514581 486663190 -242518671 337668386 999215523 746750082 975645653 257458899 589712130 -123743308 583663272 894458166 280353222 157069774 15929484 380801257 351285801 -294094478 962774361 429288997 917391381 373973523 587493899 580062253 19062877...

output:

1479061343

result:

ok 1 number(s): "1479061343"

Test #10:

score: 0
Accepted
time: 56ms
memory: 395260kb

input:

5000 4555
32276812 -405257787 928826356 1936603 708485596 301256741 176477041 209245369 435370391 63590094 582143858 485389936 436535852 -883233248 988101496 526816751 586398048 253729353 188188962 307451400 357347908 515050134 5186448 535195778 244200595 560492976 807777963 77495694 616380893 -2363...

output:

2073230674059

result:

ok 1 number(s): "2073230674059"

Test #11:

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

input:

5000 4571
922815163 886687794 600504043 88070933 974456610 410817584 479031631 80822352 535088772 675397399 483609355 713320973 946923086 -347755895 318910790 527771556 966071802 55421640 65481148 234101543 699846504 777474987 342565827 272506339 939606030 83448918 954433099 501300208 410729227 8297...

output:

-3891478

result:

ok 1 number(s): "-3891478"

Test #12:

score: 0
Accepted
time: 39ms
memory: 395064kb

input:

5000 1409
181949731 958052383 903585512 174205264 650493041 -594007355 118022709 288835823 634807153 -287204702 311445924 646284719 498779515 107245833 649720085 865162850 -935680139 152081218 942773334 865784395 410941319 629834422 679945207 378413120 971447953 680033788 469684453 293700941 2050775...

output:

2221363607186

result:

ok 1 number(s): "2221363607186"

Test #13:

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

input:

5000 3299
72488080 439482389 501634271 670405012 916464056 408600905 51981079 160412806 70962021 193979298 917944130 800586828 9166748 866735773 685562088 866117655 315353892 617337017 820065520 792434538 48407206 850790078 17324586 -779287194 666853386 866553242 -616339589 86101674 335862382 532869...

output:

1617908929

result:

ok 1 number(s): "1617908929"

Test #14:

score: 0
Accepted
time: 80ms
memory: 394780kb

input:

5000 1001
331622650 215879686 468279251 756539343 551031290 591790676 59568377 663393570 -170680402 437190382 450813407 733550573 855990471 36291127 -384967603 867072460 -989994938 713996596 992324998 719084681 759502021 113214929 649671257 516597755 -993662601 758105403 131590944 509906188 42517800...

output:

2087483384058

result:

ok 1 number(s): "2087483384058"

Test #15:

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

input:

5000 1719
-617898668 -614988385 -924598922 -227756070 -10818096 -404529485 -360613370 -528639445 -447593599 -900483874 -809552895 -47179441 -188236695 -856837968 -948109071 -561054704 -988424287 -398047675 -578215418 254978826 -264566965 -907327637 -583701525 -243272794 -762297189 -556924717 -489198...

output:

-4476415

result:

ok 1 number(s): "-4476415"

Test #16:

score: -100
Runtime Error

input:

5000 3204
-508437017 -465014610 -891243901 313890401 -276789111 -587719256 -999604449 -736652917 -547311980 -512291177 -5985683 -570077770 -403656637 -321360614 -278918365 -562009509 -368098040 -494707254 -455507604 -181628969 -975661781 -464719781 -921080905 -349179575 -457702623 -448476879 -340885...

output:


result: