Submission #45626

#	Time	Username	Problem	Language	Result	Execution time	Memory
45626		evenharder	Beads and wires (APIO14_beads)	C++11	0 / 100	9 ms	8196 KiB

beads

#include <stdio.h>
#include <algorithm>
#include <vector>

typedef long long int lld;
struct edge
{
    lld x, d;
};
const int MAX_N = 200001;
const lld INF = 2e9 + 2e5;
lld dp0[MAX_N];
lld dp1[MAX_N];
int parent[MAX_N];
lld cost[MAX_N];
std::vector<edge> g[MAX_N];
int n;

void dfs_tree(int cur, int par)
{
    for(edge& e : g[cur])
    {
        if(e.x != par)
        {
            cost[e.x] = e.d;
            parent[e.x] = cur;
            dfs_tree(e.x, cur);
        }
    }
}

inline int child_num(int cur)
{
    return cur == 1 ? g[cur].size() : g[cur].size() - 1;
}
lld getDP0(int cur);
lld getDP1(int cur);

lld getDP0(int cur)
{
    lld& ret = dp0[cur];
    if(~ret) return ret;

    ret = 0;

    for(edge& e : g[cur])
    {
        if(e.x == parent[cur]) continue;
        ret += std::max(getDP0(e.x), cost[e.x]+getDP1(e.x));
    }

    if(child_num(cur) >= 2)
    {
        lld offset[3] = {-INF, -INF, };
        for(edge& e : g[cur])
        {
            if(e.x == parent[cur]) continue;
            lld temp = std::max(getDP0(e.x), cost[e.x]+getDP1(e.x));
            offset[2] = cost[e.x]+getDP0(e.x) - temp;
            for(int i=2;i;i--)
            {
                if(offset[i-1] < offset[i])
                    std::swap(offset[i-1], offset[i]);
                else break;
            }
        }
        ret = std::max(ret, ret + offset[0] + offset[1]);
    }
    return ret;
}
lld getDP1(int cur)
{
    lld& ret = dp1[cur];
    if(~ret) return ret;
    ret = -INF;
    if(child_num(cur) >= 1)
    {
        lld offset = -INF;
        lld sum = 0;
        for(edge& e : g[cur])
        {
            if(e.x == parent[cur]) continue;
            lld temp = std::max(getDP0(e.x), cost[e.x]+getDP1(e.x));
            sum += temp;
            offset = std::max(offset, cost[e.x]+getDP0(e.x) - temp);
        }
        ret = sum + offset;
    }
    return ret;
}
int main()
{
    scanf("%d", &n);
    for(int i=1;i<n;i++)
    {
        int a,b,e;
        scanf("%d%d%d",&a,&b,&e);
        g[a].push_back({b,e});
        g[b].push_back({a,e});
    }
    dfs_tree(1,-1);
    std::fill(dp0, dp0+MAX_N, -1);
    std::fill(dp1, dp1+MAX_N, -1);

    printf("%lld", getDP0(1));
}

Compilation message (stderr)

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

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