Submission #106586

#	Time	Username	Problem	Language	Result	Execution time	Memory
106586		Kastanda	Beads and wires (APIO14_beads)	C++11	100 / 100	244 ms	20460 KiB

beads

#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], dp2[N][2];
vector < pair < int , int > > Adj[N];
void DFS(int v, int p, int w)
{
    int Mx = 0;
    for (auto &u : Adj[v])
        if (u.x != p)
        {
            DFS(u.x, v, u.y);
            dp[v][0] += dp[u.x][1];
            Mx = max(Mx, dp[u.x][0] + u.y + w - dp[u.x][1]);
        }
    dp[v][1] = dp[v][0] + Mx;
}
void DFS2(int v, int p, int w)
{
    dp2[v][0] = dp[v][0];
    dp2[v][1] = dp[v][1];
    int sum = 0, MX[] = {INT_MIN, INT_MIN};
    for (auto &u : Adj[v])
        if (u.x != p)
        {
            DFS2(u.x, v, u.y);
            sum += dp[u.x][1];
            if (MX[1] < dp[u.x][0] + u.y - dp[u.x][1])
                MX[1] = dp[u.x][0] + u.y - dp[u.x][1];
            if (MX[0] < MX[1])
                swap(MX[0], MX[1]);
        }
    for (auto &u : Adj[v])
        if (u.x != p)
        {
            bool tp = (MX[0] == dp[u.x][0] + u.y - dp[u.x][1]);
            dp2[v][0] = max(dp2[v][0], dp2[u.x][1] + sum - dp[u.x][1]);
            dp2[v][0] = max(dp2[v][0], dp2[u.x][0] + u.y + sum - dp[u.x][1] + MX[tp]);
            dp2[v][1] = max(dp2[v][1], dp2[v][0]);
            dp2[v][1] = max(dp2[v][1], dp2[u.x][0] + u.y + w + sum - dp[u.x][1]);
        }
}
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);
    DFS2(1, 0, 0);
    return !printf("%d", dp2[1][0]);
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:48:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:52: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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43