Submission #755025

#	Time	Username	Problem	Language	Result	Execution time	Memory
755025		ttamx	Beads and wires (APIO14_beads)	C++14	100 / 100	135 ms	21564 KiB

beads

#include<bits/stdc++.h>

using namespace std;

const int N=2e5+5;

int n;
vector<pair<int,int>> adj[N];
int dp[N][4];

void dfs(int u,int p=0){
    pair<pair<int,int>,pair<int,int>> mx={{-1e9,-1},{-1e9,-1}},mx2={{-1e9,-1},{-1e9,-1}};
    int c0=-1e9;
    for(auto [v,w]:adj[u]){
        if(v==p)continue;
        dfs(v,u);
        int res=max(dp[v][0],dp[v][2]+w);
        dp[u][0]+=res;
        dp[u][1]+=res;
        dp[u][2]+=res;
        dp[u][3]+=res;
        mx.second=max(mx.second,{dp[v][0]+w-res,v});
        if(mx.second>mx.first)swap(mx.first,mx.second);
        mx2.second=max(mx2.second,{dp[v][1]+w-res,v});
        if(mx2.second>mx2.first)swap(mx2.first,mx2.second);
        c0=max(c0,max(dp[v][1],dp[v][3]+w)-res);
    }
    int c1=mx.first.first+max(mx.second.first,mx.first.second!=mx2.first.second?mx2.first.first:mx2.second.first);
    int c2=mx2.first.first+(mx2.first.second!=mx.first.second?mx.first.first:mx.second.first);
    dp[u][1]+=max({c0,c1,c2});
    dp[u][2]+=mx.first.first;
    dp[u][3]+=mx2.first.first;
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<n;i++){
        int u,v,w;
        cin >> u >> v >> w;
        adj[u].emplace_back(v,w);
        adj[v].emplace_back(u,w);
    }
    dfs(1);
    cout << max(dp[1][0],dp[1][1]);
}

Compilation message (stderr)

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

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