Submission #1178109

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178109		InvMOD	Beads and wires (APIO14_beads)	C++20	100 / 100	139 ms	41400 KiB

beads

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()

void solve()
{
    int n; cin >> n;

    vector<vector<pair<int,int>>> adj(n + 1);
    for(int i = 0; i < n - 1; i++){
        int u,v,c; cin >> u >> v >> c;
        adj[u].emplace_back(v, c);
        adj[v].emplace_back(u, c);
    }

    vector<vector<int>> dp(n + 1, vector<int>(2, 0)), sdp(n + 1, vector<int>());

    const int inf = 2e9;
    function<void(int,int)> calc_dp = [&](int x, int p) -> void{
        for(int i = 0; i < 2; i++) sdp[x].push_back(-inf);

        for(auto [v, w] : adj[x])if(v != p){
            calc_dp(v, x);

            dp[x][0] = dp[x][0] + max(dp[v][1] + w, dp[v][0]);
            sdp[x].push_back(-max(dp[v][1] + w, dp[v][0]) + (dp[v][0] + w));
        }
        sort(all(sdp[x]), greater<int>());

        dp[x][1] = dp[x][0] + sdp[x][0];
    };
    calc_dp(1, -1);

    int answer = 0;
    function<void(int,int)> reroot = [&](int x, int p) -> void{
        answer = max(answer, dp[x][0]);
        for(auto [v, w] : adj[x])if(v != p){
            int ndp0 = dp[x][0] - max(dp[v][1] + w, dp[v][0]);
            int ndp1 = ndp0;

            int sdpv = -max(dp[v][1] + w, dp[v][0]) + (dp[v][0] + w);
            if(sdp[x][0] != sdpv){
                ndp1 = ndp0 + sdp[x][0];
            }
            else ndp1 = ndp0 + sdp[x][1];

            dp[v][0] = dp[v][0] + max(ndp1 + w, ndp0);
            sdp[v].push_back(-max(ndp1 + w, ndp0) + (ndp0 + w));

            sort(all(sdp[v]), greater<int>());
            dp[v][1] = dp[v][0] + sdp[v][0];

            reroot(v, x);
        }
    };
    reroot(1, -1);

    cout << answer << "\n";
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    #define name "InvMOD"
    if(fopen(name".INP", "r")){
        freopen(name".INP","r",stdin);
        freopen(name".OUT","w",stdout);
    }

    int t = 1; //cin >> t;
    while(t--) solve();
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:72:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |         freopen(name".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
beads.cpp:73:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   73 |         freopen(name".OUT","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

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