QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#404874#6298. ColoringwaretleRE 52ms199732kbC++141.8kb2024-05-04 21:04:572024-05-04 21:04:59

Judging History

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

  • [2024-05-04 21:04:59]
  • 评测
  • 测评结果:RE
  • 用时:52ms
  • 内存:199732kb
  • [2024-05-04 21:04:57]
  • 提交

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...

output:


result: