Submission #409883

#	Time	Username	Problem	Language	Result	Execution time	Memory
409883		tengiz05	Beads and wires (APIO14_beads)	C++17	28 / 100	1090 ms	852 KiB

beads

#include <bits/stdc++.h>
using i64 = long long;
constexpr int N = 1e4;
int n;
std::vector<std::pair<int, int>> e[N];
int dp[N][2];
void dfs(int u, int p, int W = 0){
    dp[u][1] = 0;
    dp[u][0] = 0;
    std::set<std::pair<int, int>> s;
    for (auto [v, w] : e[u]) {
        if (v != p) {
            dfs(v, u, w);
            dp[u][0] += dp[v][1];
            s.emplace(dp[v][0] - dp[v][1] + w, v);
        }
    }
    dp[u][1] = dp[u][0];
    if (p == -1) {
        if (s.size() > 1) {
            int mx1 = s.rbegin() -> first;
            int id1 = s.rbegin() -> second;
            s.erase(*s.rbegin());
            int mx2 = s.rbegin() -> first;
            int id2 = s.rbegin() -> second;
            s.erase(*s.rbegin());
            dp[u][1] += mx1 + mx2;
            dp[u][1] = std::max(dp[u][1], dp[u][0]);
        }
    } else {
        if (s.size() > 0) {
            int mx = s.rbegin() -> first;
            int id = s.rbegin() -> second;
            s.erase(*s.rbegin());
            dp[u][1] += mx + W;
            dp[u][1] = std::max(dp[u][1], dp[u][0]);
        }
    }
}
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        u--;
        v--;
        e[u].emplace_back(v, w);
        e[v].emplace_back(u, w);
    }
    int ans = 0;
    for (int i = 0; i < n; i++) {
        dfs(i, -1);
        ans = std::max(ans, dp[i][1]);
    }
    std::cout << ans << "\n";
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int, int)':
beads.cpp:22:17: warning: unused variable 'id1' [-Wunused-variable]
   22 |             int id1 = s.rbegin() -> second;
      |                 ^~~
beads.cpp:25:17: warning: unused variable 'id2' [-Wunused-variable]
   25 |             int id2 = s.rbegin() -> second;
      |                 ^~~
beads.cpp:33:17: warning: unused variable 'id' [-Wunused-variable]
   33 |             int id = s.rbegin() -> second;
      |                 ^~

• Subtask 1: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43