QOJ.ac

QOJ

IDSubmission IDProblemHackerOwnerResultSubmit timeJudge time
#325#86781#4406. 独立集问题CrysflyCrysflyFailed.2023-03-10 21:48:092023-03-10 21:48:12

Details

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)

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#86781#4406. 独立集问题Crysfly97 153ms115264kbC++141.6kb2023-03-10 21:42:362023-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;
}