# | TimeUTC-0 | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1043579 | EntityPlantt | Beads and wires (APIO14_beads) | C++17 | 1 ms | 5164 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |