QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#87443 | #4406. 独立集问题 | Ignotus | 0 | 66ms | 75740kb | C++14 | 2.1kb | 2023-03-12 22:24:37 | 2023-03-12 22:24:40 |
Judging History
answer
#include <bits/stdc++.h>
template <typename T>
void rd(T& x){
x = 0; char c = getchar(); int f = 1;
while(!isdigit(c)) f = c == '-' ? -1 : 1, c = getchar();
while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
x *= f;
}
template <typename T, typename... Args>
void rd(T& x, Args&... args){rd(x); rd(args...);}
using ll = long long;
const int N = 4.1e5 + 10;
const ll INF = 1e18;
int n, a[N];
ll f[N][3][2];
/*
0/1/2: 初始的权值被父亲吸走/被儿子吸走/自己去吸(初始权值被吸走后还可以操作这个点,这时不影响答案)
相邻点不可能同时选 2 状态
0/1: 当前点是否吸走父亲的初始权值
*/
std::vector <int> G[N];
void dp(int x, int fath){
for(auto y : G[x]) dp(y, x);
ll sum1 = 0, sum2 = 0, dim = INF;
for(auto y : G[x]){
ll t = std::max({f[y][0][0] - a[y], f[y][1][0], f[y][2][0]});
sum1 += t;
sum2 += std::max({f[y][0][0] - a[y], f[y][1][0]});
dim = std::min(dim, t - std::max(f[y][1][1], f[y][2][1])); // 去掉一个子树的贡献,因为这个子树要吸走 x
}
f[x][0][0] = sum1;
f[x][1][0] = sum1 - dim, f[x][1][1] = sum1 - dim - a[fath];
f[x][2][0] = sum2 + a[x], f[x][2][1] = sum2 - a[fath];
sum1 = 0, sum2 = 0, dim = INF;
for(auto y : G[x]){
ll t = std::max({f[y][0][0] + a[y], f[y][1][0], f[y][2][0]});
sum1 += t;
sum2 += std::max({f[y][0][0] + a[y], f[y][1][0]});
dim = std::min(dim, t - std::max(f[y][1][1], f[y][2][1])); // 去掉一个子树的贡献,因为这个子树要吸走 x
}
f[x][0][0] = std::max(f[x][0][0], sum1);
f[x][1][0] = std::max(f[x][1][0], sum1 - dim), f[x][1][1] = std::max(f[x][1][1], sum1 - dim + a[fath]);
f[x][2][0] = std::max(f[x][2][0], sum2 - a[x]), f[x][2][1] = std::max(f[x][2][1], sum2 + a[fath]);
}
int main(){
rd(n);
for(int i = 1; i <= n; ++i) rd(a[i]);
for(int i = 2, x; i <= n; ++i) rd(x), G[x].push_back(i);
dp(1, 0);
printf("%lld\n", std::max(f[1][1][0], f[1][2][0]));
return 0;
}
詳細信息
Subtask #1:
score: 0
Wrong Answer
Test #1:
score: 0
Wrong Answer
time: 31ms
memory: 75740kb
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:
175477002774468
result:
wrong answer 1st numbers differ - expected: '175477002777567', found: '175477002774468'
Subtask #2:
score: 0
Wrong Answer
Test #21:
score: 0
Wrong Answer
time: 66ms
memory: 42000kb
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:
175766699895849
result:
wrong answer 1st numbers differ - expected: '175766699890054', found: '175766699895849'
Subtask #3:
score: 0
Wrong Answer
Test #41:
score: 0
Wrong Answer
time: 2ms
memory: 16560kb
input:
7 247522519 398923496 -976223527 806215585 -937536479 -130552271 90576461 1 2 1 2 5 5
output:
3496973877
result:
wrong answer 1st numbers differ - expected: '3587550338', found: '3496973877'
Subtask #4:
score: 0
Skipped
Dependency #3:
0%
Subtask #5:
score: 0
Skipped
Dependency #4:
0%
Subtask #6:
score: 0
Skipped
Dependency #1:
0%