QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#359764 | #6298. Coloring | zhouhuanyi | WA | 1ms | 4332kb | C++23 | 1.2kb | 2024-03-20 20:42:43 | 2024-03-20 20:42:44 |
Judging History
answer
#include<iostream>
#include<cstdio>
#include<vector>
#define N 5000
using namespace std;
const long long inf=(long long)(1e18);
int read()
{
char c=0;
int sum=0,f=1;
while (c!='-'&&(c<'0'||c>'9')) c=getchar();
if (c=='-') c=getchar(),f=-1;
while ('0'<=c&&c<='9') sum=sum*10+c-'0',c=getchar();
return sum*f;
}
int n,s,w[N+1],p[N+1],fa[N+1],a[N+1];
long long dp[N+1][3],ans;
vector<int>E[N+1];
bool used[N+1];
void dfs(int x)
{
long long res;
for (int op=1;op<=2;++op) dp[x][op]=w[x]*(op==1)-p[x]*op;
used[x]=1;
for (int i=0;i<E[x].size();++i)
if (!used[E[x][i]])
{
fa[E[x][i]]=x,dfs(E[x][i]);
for (int op=1;op<=2;++op)
{
res=0;
for (int opt=1;opt<=op;++opt) res=max(res,dp[E[x][i]][opt]);
dp[x][op]+=res;
}
}
return;
}
int main()
{
vector<int>sp;
n=read(),s=read();
for (int i=1;i<=n;++i) w[i]=read();
for (int i=1;i<=n;++i) p[i]=read();
for (int i=1;i<=n;++i) a[i]=read(),E[a[i]].push_back(i);
dfs(s);
if (a[a[s]]!=s) printf("%lld\n",max(dp[s][1],dp[s][2])+p[s]);
else
{
ans=dp[s][1]-p[s];
for (int i=0;i<E[s].size();++i)
if (E[s][i]!=a[s])
sp.push_back(E[s][i]);
E[s]=sp,dfs(s),printf("%lld\n",max(dp[s][1],dp[s][2])-p[s]);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 4080kb
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: 3860kb
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: 1ms
memory: 4240kb
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: -100
Wrong Answer
time: 1ms
memory: 4332kb
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:
472582069
result:
wrong answer 1st numbers differ - expected: '484763000532', found: '472582069'