QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#625910 | #4406. 独立集问题 | Kevin5307 | 0 | 56ms | 60620kb | C++23 | 1.4kb | 2024-10-09 21:41:52 | 2024-10-09 21:41:52 |
Judging History
answer
//Author: Kevin
#include<bits/stdc++.h>
//#pragma GCC optimize("O2")
using namespace std;
#define ll long long
#define ull unsigned ll
#define pb emplace_back
#define mp make_pair
#define ALL(x) (x).begin(),(x).end()
#define rALL(x) (x).rbegin(),(x).rend()
#define srt(x) sort(ALL(x))
#define rev(x) reverse(ALL(x))
#define rsrt(x) sort(rALL(x))
#define sz(x) (int)(x.size())
#define inf 0x3f3f3f3f
#define pii pair<int,int>
#define lb(v,x) (int)(lower_bound(ALL(v),x)-v.begin())
#define ub(v,x) (int)(upper_bound(ALL(v),x)-v.begin())
#define uni(v) v.resize(unique(ALL(v))-v.begin())
#define longer __int128_t
void die(string S){puts(S.c_str());exit(0);}
ll d[500500];
int p[500500],n;
vector<int> G[500500];
ll f[500500][2],g[500500][2],h[500500];
void dfs(int u)
{
for(auto v:G[u])
dfs(v);
ll tmp[2]={0,0};
for(auto v:G[u])
{
ll w0=max({f[v][0],f[v][1],h[u]});
ll w1=max(f[v][0]-d[u],f[v][1]+d[u]);
tmp[1]=max(tmp[1]+w0,tmp[0]+w1);
tmp[0]+=w0;
}
h[u]=tmp[1];
for(auto v:G[u])
{
f[u][0]+=g[v][0];
f[u][1]+=g[v][1];
}
f[u][0]+=d[u];
f[u][1]-=d[u];
g[u][0]=max(tmp[1],tmp[0]-d[u]);
g[u][1]=max(tmp[1],tmp[0]+d[u]);
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin>>n;
for(int i=1;i<=n;i++)
cin>>d[i];
for(int i=2;i<=n;i++)
cin>>p[i];
for(int i=2;i<=n;i++)
G[p[i]].pb(i);
dfs(1);
cout<<h[1]<<endl;
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 51ms
memory: 60620kb
input:
351493 -641495974 -401868912 -864400429 35718599 -579296290 767835327 149511992 -246228754 649472235 893048442 -292675192 -788090312 -578172296 -62289673 196890164 -120059197 -452848333 -216788131 -604555771 -240241020 376984486 -407661514 -107574590 -461679558 -470560314 -583391402 -991686079 76956...
output:
159960496782634
result:
wrong answer 1st numbers differ - expected: '175477002777567', found: '159960496782634'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 56ms
memory: 40604kb
input:
351493 915594742 688454502 456077914 208864399 625937959 102483811 538999077 529481828 400375958 387560315 83710527 83424975 330114353 684812426 68052931 28849220 295907801 535129167 967891325 124069427 644256858 757666812 558755455 178666038 177054898 795236216 848264282 669310447 328353372 3681163...
output:
128071837446874
result:
wrong answer 1st numbers differ - expected: '175766699890054', found: '128071837446874'
Subtask #3:
score: 0
Wrong Answer
Test #41:
score: 0
Wrong Answer
time: 0ms
memory: 7816kb
input:
7 247522519 398923496 -976223527 806215585 -937536479 -130552271 90576461 1 2 1 2 5 5
output:
3340027819
result:
wrong answer 1st numbers differ - expected: '3587550338', found: '3340027819'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%