Submission #1043579

#TimeUTC-0UsernameProblemLanguageResultExecution timeMemory
10435792024-08-04 11:40:11EntityPlanttBeads and wires (APIO14_beads)C++17
0 / 100
1 ms5164 KiB
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e5 + 5, INF = 1e7;
// dp[node/subtree][blue pair incomplete?] = sum of blue wires in subtree
int dp[N][2];
vector <pair <int, int>> adj[N];
void dfs(int node, int parent, int pweight) {
int sum = 0, bestblue = -INF, bestblue2 = -INF, bestblueadd;
for (auto &[u, w] : adj[node]) {
if (u == parent) continue;
dfs(u, node, w);
sum += dp[u][0];
if (bestblue <= dp[u][1] - dp[u][0]) {
bestblue2 = bestblue;
bestblue = dp[u][1] - dp[u][0];
}
else bestblue2 = max(bestblue2, dp[u][1] - dp[u][0]);
}
bestblueadd = max(0, bestblue + bestblue2);
dp[node][0] = max(sum + bestblueadd, sum + pweight + bestblue);
dp[node][1] = sum + pweight + bestblueadd;
// cerr << "dp[" << node << "] = {" << dp[node][0] << ", " << dp[node][1] << "}\n";
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...