QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#87157#4406. 独立集问题Fideow0 37ms58420kbC++142.3kb2023-03-11 20:19:092023-03-11 20:19:10

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-03-11 20:19:10]
  • 评测
  • 测评结果:0
  • 用时:37ms
  • 内存:58420kb
  • [2023-03-11 20:19:09]
  • 提交

answer

//贺的 wlxhkk 神仙的 [双手合十] 

#include <iostream>
#include <cstdio>

#define maxn 355555
#define inf 0x3f3f3f3f3f3f3f3f
#define int long long

using namespace std;

inline int read(){
	int x = 0, flag = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9'){
		x = (x << 3) + (x << 1) + ch - '0';
		ch = getchar();
	}
	return x * flag;
}

int hd[maxn], cnt;
struct edge{
	int v, nxt;
}e[maxn << 1];
void add(int u, int v){
	e[++cnt].v = v;
	e[cnt].nxt = hd[u];
	hd[u] = cnt;
	return;
}

int max(int x, int y, int z){
	return max(max(x, y), z);
}

int n, f[maxn][3][2], g[3][2], a[maxn], tmp;
//结局 儿子 | 自己 | 父亲
//父亲有没有被选。
//考虑中间这次。

void dfs(int u, int fa){
	for(int i = hd[u]; i; i = e[i].nxt){
		int v = e[i].v;
		dfs(v, u);
	}
	for(int i = 0; i <= 2; ++i)
		for(int j = 0; j <= 1; ++j)
			g[i][j] = 0;
	tmp = 0;
	g[0][0] = -inf;
	g[1][0] = -a[u];
	for(int i = hd[u]; i; i = e[i].nxt){
		int v = e[i].v;
		g[0][0] = max(g[0][0] + max(f[v][0][0], f[v][1][0], f[v][2][0] + a[v]), tmp + max(f[v][0][1], f[v][2][1]));
		tmp += max(f[v][0][0], f[v][1][0], f[v][2][0] + a[v]);
		g[1][0] += max(f[v][2][0] + a[v], f[v][0][0]);
		g[2][0] += max(f[v][2][0] + a[v], f[v][1][0], f[v][0][0]);
	}
	g[0][1] = g[0][0] + a[fa];
	g[1][1] = g[1][0] + a[fa];
	for(int i = 0; i <= 2; ++i)
		for(int j = 0; j <= 1; ++j)
			f[u][i][j] = g[i][j], g[i][j] = 0;
	tmp = 0;
	g[0][0] = -inf;
	g[1][0] = a[u];
	for(int i = hd[u]; i; i = e[i].nxt){
		int v = e[i].v;
		g[0][0] = max(g[0][0] + max(f[v][0][0], f[v][1][0], f[v][2][0] - a[v]), tmp + max(f[v][0][1], f[v][2][1]));
		tmp += max(f[v][0][0], f[v][1][0], f[v][2][0] - a[v]);
		g[1][0] += max(f[v][2][0] - a[v], f[v][0][0]);
		g[2][0] += max(f[v][2][0] - a[v], f[v][1][0], f[v][0][0]);
	}
	g[0][1] = g[0][0] - a[fa];
	g[1][1] = g[1][0] - a[fa];
	for(int i = 0; i <= 2; ++i)
		for(int j = 0; j <= 1; ++j)
			f[u][i][j] = max(f[u][i][j], g[i][j]);
	return;
}

signed main(){
	n = read();
	for(int i = 1; i <= n; ++i) a[i] = read();
	for(int i = 2; i <= n; ++i){
		int p = read();
		add(p, i);
	}
	dfs(1, 0);
	printf("%lld", max(f[1][0][0], f[1][1][0]));
	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: 37ms
memory: 58420kb

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:

175476286027231

result:

wrong answer 1st numbers differ - expected: '175477002777567', found: '175476286027231'

Subtask #2:

score: 0
Wrong Answer

Test #21:

score: 0
Wrong Answer
time: 27ms
memory: 32100kb

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:

175766696035683

result:

wrong answer 1st numbers differ - expected: '175766699890054', found: '175766696035683'

Subtask #3:

score: 0
Wrong Answer

Test #41:

score: 0
Wrong Answer
time: 2ms
memory: 3436kb

input:

7
247522519 398923496 -976223527 806215585 -937536479 -130552271 90576461
1 2 1 2 5 5

output:

3092505300

result:

wrong answer 1st numbers differ - expected: '3587550338', found: '3092505300'

Subtask #4:

score: 0
Skipped

Dependency #3:

0%

Subtask #5:

score: 0
Skipped

Dependency #4:

0%

Subtask #6:

score: 0
Skipped

Dependency #1:

0%