QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#404874 | #6298. Coloring | waretle | RE | 52ms | 199732kb | C++14 | 1.8kb | 2024-05-04 21:04:57 | 2024-05-04 21:04:59 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=5005;
int n,rt,to[N],q[N],hd=1,tl,deg[N];
ll p[N],w[N],dp[N][N],s0[N],s1[N];
bool vis[N];
vector<int>g[N];
void dfs(int u)
{
for(int i=1;i<=n;++i)dp[u][i]=(i&1?w[u]:0)-i*p[u];
for(int v:g[u])
{
dfs(v);
ll mx=0;
for(int i=1;i<=n;++i)mx=max(mx,dp[v][i]),dp[u][i]+=mx;
}
}
int main()
{
scanf("%d%d",&n,&rt);
for(int i=1;i<=n;++i)scanf("%lld",w+i);
for(int i=1;i<=n;++i)scanf("%lld",p+i);
for(int i=1;i<=n;++i)scanf("%d",to+i),g[to[i]].push_back(i),++deg[to[i]];
for(int i=1;i<=n;++i)if(!g[i].size())q[++tl]=i;
while(hd<=tl)
{
int u=q[hd++];
if(!--deg[to[u]])vis[to[u]]=1,q[++tl]=to[u];
}
if(vis[rt])
{
dfs(rt);
printf("%lld\n",max(dp[rt][1],dp[rt][2])+p[rt]);
}
else
{
vector<int>cir;
for(int u=rt;!vis[u];u=to[u])cir.push_back(u),vis[u]=1;
for(int i=0;i<cir.size();++i)
g[cir[i]].erase(find(g[cir[i]].begin(),g[cir[i]].end(),i==0?cir.back():cir[i-1]));
reverse(cir.begin()+1,cir.end());
for(int i:cir)dfs(i);
if(cir.size()==2)
printf("%lld\n",max({dp[rt][1],dp[rt][2],dp[rt][1]+dp[cir[1]][1]})+p[rt]);
else
{
ll ans=-1e18;
for(int x=1;x<=n;++x)
{
ll s0=dp[rt][x],s1=dp[rt][x],s2=dp[rt][x];
for(int i=1;i<cir.size();++i)
{
if(x>1)s0+=dp[cir[i]][x-2];
s1+=dp[cir[i]][x-1],s2+=dp[cir[i]][x];
s1=max(s1,s2),s0=max(s0,s1);
}
ans=max(ans,x==1?s1:s0);
}
printf("%lld\n",ans+p[rt]);
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1ms
memory: 5920kb
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: 4188kb
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: 198848kb
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: 52ms
memory: 199732kb
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: -100
Runtime Error
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...