Submission #1149982

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149982		12345678	Beads and wires (APIO14_beads)	C++17	0 / 100	2 ms	4936 KiB

beads

#include <bits/stdc++.h>

using namespace std;

const int nx=2e5+5;

int n, u, v, w, dp1[nx], dp2[nx], res;
vector<pair<int, int>> d[nx];

void dfs(int u, int p, int pw)
{
    dp1[u]=dp2[u]=0;
    int sm=0;
    vector<pair<int, int>> c;
    for (auto [v, w]:d[u]) if (v!=p) dfs(v, u, w), dp1[u]+=dp2[v], sm+=dp2[v], c.push_back({v, w});
    for (int i=0; i<c.size(); i++) 
    {
        for (int j=i+1; j<c.size(); j++) 
        {
            dp1[u]=max(dp1[u], sm-dp2[c[i].first]-dp2[c[j].first]+dp1[c[i].first]+dp1[c[j].first]+c[i].second+c[j].second);
        }
    }
    for (int i=0; i<c.size(); i++) dp2[u]=max(dp2[u], sm-dp2[c[i].first]+dp1[c[i].first]+c[i].second+pw);
    dp2[u]=max(dp2[u], dp1[u]);
}

int main()
{
    cin.tie(NULL)->sync_with_stdio(false);
    cin>>n;
    for (int i=1; i<n; i++) cin>>u>>v>>w, d[u].push_back({v, w}), d[v].push_back({u, w});
    dfs(1, 1, 0);
    res=dp1[1];
    for (int st=1; st<=n; st++)
    {
        dfs(st, st ,0);
        if (dp1[st]!=res) cout<<1/0;
    }
    dfs(1, 1, 0);
    cout<<dp1[1];
}

/*
11 34
35 95
0 0
*/

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:37:34: warning: division by zero [-Wdiv-by-zero]
   37 |         if (dp1[st]!=res) cout<<1/0;
      |                                 ~^~

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