Submission #469218

#	Time	Username	Problem	Language	Result	Execution time	Memory
469218		amirmohammad_nezami	Beads and wires (APIO14_beads)	C++14	100 / 100	201 ms	22284 KiB

beads

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

#define F first
#define S second
#define PB push_back
#define _sz(e) e.size()
#define pii pair <int , int>
#define FAST ios::sync_with_stdio(0); cin.tie(0);

const int maxn = 2e5 + 4 , N = 1e6 + 4 , mod = 1e9 + 7 , INF = 1e9;

int n , dp[maxn] , gp[maxn] , zp[maxn];
vector <pii> edges[maxn];

void dfs(int v , int p = -1 , int W = 0) {
    for (auto u : edges[v]) {
        if(u.F != p) dfs(u.F , v , u.S); 
    }
    for (auto u : edges[v]) {
        if(u.F != p) {
            dp[v] += max(dp[u.F] , gp[u.F]);
        }
    }
    for (auto u : edges[v]) {
        if(u.F != p) {
            int others = dp[v] - max(dp[u.F] , gp[u.F]);
            gp[v] = max(gp[v] , dp[u.F] + u.S + W + others);
        }
    }

    zp[v] = dp[v];
    int mx1 = -INF , mx2 = -INF;
    for (auto u : edges[v]) {
        if(u.F != p) {
            int val = dp[u.F] + u.S - max(dp[u.F] , gp[u.F]);
            if(val > mx1) {
                mx2 = mx1; 
                mx1 = val;
            }
            else if(val > mx2) {
                mx2 = val;
            }
        }
    }
    for (auto u : edges[v]) {
        if(u.F != p) {
            int others = dp[v] - max(dp[u.F] , gp[u.F]);
            int val = (mx1 == dp[u.F] + u.S - max(dp[u.F] , gp[u.F]) ? mx2 : mx1);

            zp[v] = max(zp[v] , zp[u.F] + others);
            zp[v] = max(zp[v] , zp[u.F] + u.S + others + val);

            for (auto x : edges[u.F]) {
                if(x.F != v) {
                    int u_others = dp[u.F] - max(dp[x.F] , gp[x.F]);
                    zp[v] = max(zp[v] , zp[x.F] + x.S + u.S + others + u_others);
                }
            }
        }
    }
}

int main() {
    FAST;
    cin >> n;
    for (int i = 0; i < n - 1; ++i) {
        int x , y , z; cin >> x >> y >> z;
        x-- , y--;
        edges[x].PB({y , z});
        edges[y].PB({x , z});
    }
    dfs(0);

    cout << zp[0] << '\n';
}

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