QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#706670#275. PalindromesTheZone0 2ms7888kbC++232.1kb2024-11-03 12:53:252024-11-03 12:53:26

Judging History

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

  • [2024-11-03 12:53:26]
  • 评测
  • 测评结果:0
  • 用时:2ms
  • 内存:7888kb
  • [2024-11-03 12:53:25]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, f[N][2], mx[N][2], ans;
vector<pair<int, int> > g[N];

void dfs(int x, int fa){
	for(auto i : g[x]){
		int y = i.first, z = i.second;
		if(y != fa){
			dfs(y, x);
			f[x][0] += max(f[y][0], f[y][1] + z);
			f[x][1] += max(f[y][0], f[y][1] + z);
			int vl = f[y][0] + z - max(f[y][0], f[y][1] + z);
			if(vl >= mx[x][0]){
				mx[x][1] = mx[x][0];
				mx[x][0] = vl; 
			} else if(vl > mx[x][1]){
				mx[x][1] = vl;
			}
		}
	}
	f[x][1] += mx[x][0];
}

void dfss(int x, int fa){
	ans = max(ans, f[x][0]);
	int a = f[x][0], b = f[x][1], c = mx[x][0], d = mx[x][1];
	for(auto i : g[x]){
		int y = i.first, z = i.second;
		if(y != fa){
			f[x][0] -= max(f[y][0], f[y][1] + z);
			f[x][1] -= max(f[y][0], f[y][1] + z);
			int vl = f[y][0] + z - max(f[y][0], f[y][1] + z);
			if(vl == mx[x][0]){
				f[x][1] = f[x][1] - mx[x][0] + mx[x][1];
			}
			f[y][0] += max(f[x][0], f[x][1] + z);
			f[y][1] += max(f[x][0], f[x][1] + z);
			f[y][1] -= mx[y][0];
			vl = f[x][0] + z - max(f[x][0], f[x][1] + z);
			if(vl >= mx[y][0]){
				mx[y][1] = mx[y][0];
				mx[y][0] = vl; 
			} else if(vl > mx[y][1]){
				mx[y][1] = vl;
			}
			f[y][1] += mx[y][0];
			dfss(y, x);
			f[x][0] = a;
			f[x][1] = b;
			mx[x][0] = c;
			mx[x][1] = d;
		}
	}
}

int main(){
	memset(mx, 0xcf, sizeof(mx));
	scanf("%d", &n);
	for(int i = 1; i < n; ++ i){
		int x, y, z;
		scanf("%d%d%d", &x, &y, &z);
		g[x].push_back(make_pair(y, z));
		g[y].push_back(make_pair(x, z));
	}
	dfs(1, 0);
	dfss(1, 0);
	printf("%d\n", ans);
	return 0;
}
/*#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 10;
int n, f[N][2], mx[N][2], ans;
vector<pair<int, int> > g[N];

void dfs(int x, int fa){
	for(auto i : g[x]){
		int y = i.first, z = i.second;
		if(y != fa){
			dfs(y, x);
			f[x][0] += max(f[y][0], f[y][1] + z);
			f[x][1] += max(f[y][0], f[y][1] + z);
			int vl = f[y][0] + z - max(f[y][0], f[y][1] + z);
			if(vl >= mx[x][0]){
				mx[x][1] = mx[x][0];
				mx[x][0] = vl; 
			} else if(vl > mx[x][1]){
				mx[x][1] = vl;
			}
		}
	}
}*/

详细

Subtask #1:

score: 0
Wrong Answer

Test #1:

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

input:

abacaba

output:

0

result:

wrong answer 1st lines differ - expected: '7', found: '0'

Subtask #2:

score: 0
Skipped

Dependency #1:

0%

Subtask #3:

score: 0
Skipped

Dependency #1:

0%

Subtask #4:

score: 0
Skipped

Dependency #1:

0%

Subtask #5:

score: 0
Skipped

Dependency #1:

0%