Submission #107430

#	Time	Username	Problem	Language	Result	Execution time	Memory
107430		evpipis	Beads and wires (APIO14_beads)	C++14	0 / 100	6 ms	4992 KiB

beads

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

#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;

const int len = 2e5+5, inf = 2e9+5;
int dp[len][2], par[len];
vector<ii> adj[len];

int solve(int u, int t){
    if (dp[u][t] != -1)
        return dp[u][t];

    int ans = 0, mx1 = -inf, mx2 = -inf;
    for (int j = 0; j < adj[u].size(); j++){
        ii v = adj[u][j];
        int temp = -inf;
        if (v.fi == par[u] && t == 0){
            temp = v.se;
        }
        else if (v.fi != par[u]){
            par[v.fi] = u;
            ans += solve(v.fi, 0);
            temp = v.se-solve(v.fi, 0)+solve(v.fi, 1);
        }

        if (temp > mx1)
            swap(mx1, mx2), mx1 = temp;
        else if (temp > mx2)
            mx2 = temp;
    }

    if (mx1 != -inf && mx2 != -inf)
        ans = max(ans, ans+mx1+mx2);
    return dp[u][t] = ans;
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i = 0; i < n-1; i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        adj[a].pb(mp(b, c));
        adj[b].pb(mp(a, c));
    }

    for (int i = 1; i <= n; i++)
        dp[i][0] = dp[i][1] = -1;

    printf("%d\n", solve(1, 0));
    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'int solve(int, int)':
beads.cpp:19:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int j = 0; j < adj[u].size(); j++){
                     ~~^~~~~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:44:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:47:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &a, &b, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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