QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
| ID | 提交记录ID | 题目 | Hacker | Owner | 结果 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|
| #325 | #86781 | #4406. 独立集问题 | Crysfly | Crysfly | Failed. | 2023-03-10 21:48:09 | 2023-03-10 21:48:12 |
详细
Extra Test:
Invalid Input
input:
## Streets 解题报告 下设 $n, m$ 同级。 设选取矩形的左右边界横坐标为 $x_1, x_2(x_1\leq x_2)$，权值为 $a_1, a_2$，上下边界的纵坐标为 $y_1, y_2(y_1\leq y_2)$，权值为 $b_1, b_2$，则矩形的代价可写为 $(x_2 - x_1)(b_1 + b_2) + (y_2 - y_1)(a_1 + a_2)$。 对于固定的 $x_2 - x_1$，我们会最小化 $a_1 + a_2$。因此，设 $va_i$ 表示当 $x_2 - x_1 = i$ 时，最小的 $a_1 + a_2$，同理设 $vb_i$ 表示当 $...
output:
result:
FAIL Expected integer, but "##" found (stdin, line 1)
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #86781 | #4406. 独立集问题 | Crysfly | 97 | 153ms | 115264kb | C++14 | 1.6kb | 2023-03-10 21:42:36 | 2023-03-10 22:03:07 |
answer
#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define int long long
using namespace std;
inline int read()
{
char c=getchar();int x=0;bool f=0;
for(;!isdigit(c);c=getchar())f^=!(c^45);
for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
return f?-x:x;
}
#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;
#define maxn 1000005
#define inf 0x3f3f3f3f3f3f3f3f
int n,fa[maxn],w[maxn][2];
vi e[maxn];
int f[maxn][2],g[maxn][2][2],mxg[maxn],mx[2];
void dfs(int u)
{
for(int v:e[u])dfs(v);
For(i,0,1)f[u][i]=w[u][i];
mx[0]=mx[1]=0;
for(int v:e[u])
For(i,0,1)mx[i]+=max(f[v][i],mxg[v]);
For(i,0,1)f[u][i]+=max(mx[0],mx[1]);
For(i,0,1)g[u][i][1]=w[u][!i];
mx[0]=mx[1]=0;
for(int v:e[u])
For(i,0,1)mx[i]+=max(f[v][i],max(g[v][0][0],g[v][1][0]));
For(i,0,1)g[u][i][1]+=mx[i];
For(i,0,1){
g[u][i][0]=-inf;
for(int v:e[u]){
For(c,0,1){
int now=w[u][c]+max(g[v][c][0],g[v][c][1]);
for(int w:e[u])
if(w!=v) now+=max(f[w][i],mxg[w]);
g[u][i][0]=max(g[u][i][0],now);
}
}
}
mxg[u]=-inf;
For(i,0,1)For(j,0,1)mxg[u]=max(mxg[u],g[u][i][j]);
// cout<<"f: "<<u<<"\n";
// For(i,0,1)cout<<f[u][i]<<" ";puts("");
// For(i,0,1)For(j,0,1)cout<<g[u][i][j]<<" \n"[j==1];
}
signed main()
{
n=read();
memset(f,-63,sizeof f);
For(i,1,n)w[i][0]=read(),w[i][1]=-w[i][0];
For(i,2,n)fa[i]=read(),e[fa[i]].pb(i);
dfs(1);
cout<<mxg[1];
return 0;
}