Submission #104276

#	Time	Username	Problem	Language	Result	Execution time	Memory
104276		Kastanda	Beads and wires (APIO14_beads)	C++11	0 / 100	7 ms	4992 KiB

beads

// Fallen
#include<bits/stdc++.h>
#define pb push_back
#define x first
#define y second
using namespace std;
const int N = 200005;
int n, dp[N][2];
vector < pair < int , int > > Adj[N];
void DFS(int v, int p, int w)
{
    int sum = 0, mn[2] = {INT_MAX, INT_MAX};
    for (auto &u : Adj[v])
        if (u.x != p)
        {
            DFS(u.x, v, u.y);
            sum += dp[u.x][0];
            if (mn[1] > dp[u.x][0] - dp[u.x][1] - u.y)
                mn[1] = dp[u.x][0] - dp[u.x][1] - u.y;
            if (mn[0] > mn[1])
                swap(mn[0], mn[1]);
        }
    dp[v][1] = max(1LL * sum, 1LL * sum - mn[0] - mn[1]);
    dp[v][0] = max(1LL * dp[v][1], 1LL * sum - mn[0] + w);
}
int main()
{
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int v, u, w;
        scanf("%d%d%d", &v, &u, &w);
        Adj[v].pb({u, w});
        Adj[u].pb({v, w});
    }
    DFS(1, 0, 0);
    return !printf("%d", dp[1][1]);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:28:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:32:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%d", &v, &u, &w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~

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