QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#706670 | #275. Palindromes | TheZone | 0 | 2ms | 7888kb | C++23 | 2.1kb | 2024-11-03 12:53:25 | 2024-11-03 12:53:26 |
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;
}
}
}
}*/
Details
Tip: Click on the bar to expand more detailed information
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%