QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#300782 | #6298. Coloring | kid_magic | WA | 0ms | 3968kb | C++14 | 2.8kb | 2024-01-08 19:58:09 | 2024-01-08 19:58:09 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
const int MAXN=5005;
int n,s;
int a[MAXN];
int w[MAXN];
int p[MAXN];
vector<int>g[MAXN];
int Rd[MAXN];
int vis[MAXN];
int Lorp[MAXN];
int cnt_lorp;
void Find_lorp(int x)
{
if(vis[x])
{
return;
}
vis[x]=1;
Lorp[++cnt_lorp]=x;
Find_lorp(a[x]);
}
bool fxw=0;
int oex[MAXN];
long long dp[MAXN][MAXN],Pre[MAXN][MAXN];
void dfs(int x,int f)
{
for(int i=0;i<g[x].size();i++)
{
int v=g[x][i];
if(v==f)
{
continue;
}
if(Rd[v])
{
continue;
}
dfs(v,x);
}
for(int i=0;i<=n+1;i++)
{
dp[x][i]=(long long)w[x]*((i&1))-((long long)i*p[x]);
for(int j=0;j<g[x].size();j++)
{
int v=g[x][j];
if(v==f)
{
continue;
}
if(Rd[v])
{
continue;
}
dp[x][i]+=Pre[v][i];
}
}
if(x==s)
{
dp[x][0]=-2e18;
}
Pre[x][0]=dp[x][0];
for(int i=1;i<=n+1;i++)
{
Pre[x][i]=max(Pre[x][i-1],dp[x][i]);
}
if(s==x)
{
fxw=1;
}
}
int Nox[MAXN];
long long F[MAXN][3];
int main()
{
// freopen("date.in","r",stdin);
// freopen("date.out","w",stdout);
scanf("%d %d",&n,&s);
oex[s]=1;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&p[i]);
}
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
g[a[i]].push_back(i);
Rd[a[i]]++;
}
queue<int>Q;
for(int i=1;i<=n;i++)
{
if(!Rd[i])
{
Q.push(i);
}
}
while(Q.size())
{
int tmp=Q.front();
Q.pop();
Rd[a[tmp]]--;
if(!Rd[a[tmp]])
{
Q.push(a[tmp]);
}
}
for(int i=1;i<=n;i++)
{
if(Rd[i]&&(!vis[i]))
{
//cerr<<i<<endl;
cnt_lorp=0;
Find_lorp(i);
for(int j=1;j<=cnt_lorp;j++)
{
//cerr<<Lorp[j]<<endl;
dfs(Lorp[j],0);
}
if(fxw)
{
if(vis[s])
{
int Sta;
for(int j=1;j<=cnt_lorp;j++)
{
if(Lorp[j]==s)
{
Sta=j;
}
}
for(int j=1;j<=cnt_lorp;j++)
{
Nox[j]=Lorp[(Sta+j-2)%cnt_lorp+1];
}
for(int j=1;j<=cnt_lorp;j++)
{
Lorp[j]=Nox[j];
//printf("%d ",Lorp[j]);
}
long long Res=-2e18;
for(int x=1;x<=n;x++)
{
F[1][0]=dp[Lorp[1]][x+1];
F[1][1]=F[1][2]=-2e18;
for(int j=2;j<=cnt_lorp;j++)
{
F[j][0]=F[j][1]=F[j][2]=-2e18;
F[j][0]=F[j-1][0]+dp[Lorp[j]][x+1];
F[j][1]=max(F[j-1][0],F[j-1][1])+dp[Lorp[j]][x];
F[j][2]=max(F[j-1][0],max(F[j-1][2],F[j-1][1]))+dp[Lorp[j]][x-1];
}
Res=max(Res,max(F[cnt_lorp][0],max(F[cnt_lorp][1],F[cnt_lorp][2])));
//printf("%d %lld %lld %lld %lld??\n",x,F[cnt_lorp][0],F[cnt_lorp][1],F[cnt_lorp][2],dp[Lorp[1]][x+1]);
}
printf("%lld\n",Res+p[s]);
}
else
{
printf("%lld\n",max(dp[s][0],dp[s][1])+p[s]);
}
return 0;
}
}
}
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3968kb
input:
3 1 -1 -1 2 1 0 0 3 1 2
output:
1
result:
ok 1 number(s): "1"
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 3912kb
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:
-34410268
result:
wrong answer 1st numbers differ - expected: '35343360', found: '-34410268'