Submission #851227

#	Time	Username	Problem	Language	Result	Execution time	Memory
851227		nonono	Beads and wires (APIO14_beads)	C++14	100 / 100	130 ms	31224 KiB

beads

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

const int mxN = 2e5 + 10;

int n;
vector<vector<pair<int, int>>> adj(mxN);
int cost[mxN];
int dp[mxN][2][2];

void dfs(int u, int fu) {
    if(adj[u].size() == 1 && fu != -1) return ;
    
    vector<pair<int, int>> L, R;
    int sum = 0, A = 0;
    
    for(auto [v, w] : adj[u]) if(v != fu) {
        cost[v] = w;
        dfs(v, u);
        
        int x = max(dp[v][0][0], dp[v][0][1]);
        sum += x;
        
        int y = max(dp[v][1][0], dp[v][1][1]);
        
        int newA = y - x;
        A = max(A, newA);
        
        L.push_back({dp[v][0][0] + w - x, v});
        R.push_back({dp[v][1][0] + w - x, v});
    }
    
    sort(L.begin(), L.end(), greater<pair<int, int>> ());
    sort(R.begin(), R.end(), greater<pair<int, int>> ());
    
    dp[u][0][0] = sum;
    dp[u][1][0] = sum + A;
    
    if(L.size() > 1) 
        dp[u][1][0] = max(dp[u][1][0], sum + L[0].first + L[1].first);
    
    if(L[0].second != R[0].second) {
        dp[u][1][0] = max(dp[u][1][0], sum + L[0].first + R[0].first);
    } else if(L.size() > 1) {
        dp[u][1][0] = max(dp[u][1][0], sum + L[0].first + R[1].first);
        dp[u][1][0] = max(dp[u][1][0], sum + L[1].first + R[0].first);
    }
    
    dp[u][0][1] = sum + cost[u] + L[0].first;
    dp[u][1][1] = sum + cost[u] + R[0].first;
}

signed main() {

    cin.tie(0)->sync_with_stdio(0);

    cin >> n;

    for(int i = 1; i <= n - 1; i ++) {
        int u, v, w;
        cin >> u >> v >> w;

        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
    }

    dfs(1, -1);

    cout << max(dp[1][0][0], dp[1][1][0]) << "\n";
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void dfs(int, int)':
beads.cpp:17:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   17 |     for(auto [v, w] : adj[u]) if(v != fu) {
      |              ^

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