QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300209 | #6298. Coloring | DJ2006 | WA | 72ms | 395264kb | C++17 | 2.3kb | 2024-01-07 21:14:15 | 2024-01-07 21:14:15 |
Judging History
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]) {
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) {
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: 5700kb
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: 1ms
memory: 5680kb
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: 16ms
memory: 74100kb
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: 51ms
memory: 394988kb
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: 7928kb
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: 72ms
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: 0ms
memory: 6144kb
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: 63ms
memory: 394888kb
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: 8108kb
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: 67ms
memory: 395068kb
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: 68ms
memory: 394816kb
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: 6220kb
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: 47ms
memory: 394804kb
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: 5992kb
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
Wrong Answer
time: 63ms
memory: 395264kb
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:
-925730663
result:
wrong answer 1st numbers differ - expected: '43714478273', found: '-925730663'