Submission #47382

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

beads

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

typedef long long int lld;
struct edge
{
    lld x, d;
};
typedef std::pair<long long int, int> dat;

const int MAX_N = 200001;
const lld INF = 2e9 + 2e5;

lld dp0[MAX_N];
lld dp1[MAX_N];
lld dp2[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 getDP2(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), getDP2(e.x)});
    }
    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), getDP2(e.x)});
            sum += temp;
            offset = std::max(offset, cost[e.x] + std::max(getDP0(e.x), getDP2(e.x)) - temp);
        }
        ret = sum + offset;
    }
    return ret;
}
lld getDP2(int cur)
{
    lld& ret = dp2[cur];
    if(~ret) return ret;
    ret = -INF;
    if(child_num(cur) >= 2)
    {
        dat offset0[3] = {dat(-INF, -1), dat(-INF, -1), dat(-INF, -1)};
        dat offset2[3] = {dat(-INF, -1), dat(-INF, -1), dat(-INF, -1)};
        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), getDP2(e.x)});
            sum += temp;
            offset0[0] = {cost[e.x] + getDP0(e.x) - temp, e.x};
            offset2[0] = {cost[e.x] + getDP2(e.x) - temp, e.x};
            std::sort(offset0, offset0+3);
            std::sort(offset2, offset2+3);
        }
        lld offset_max = offset0[1].first + offset0[2].first;
        if(offset0[2].second == offset2[2].second)
            offset_max = std::max({
                offset_max,
                offset0[1].first + offset2[2].first,
                offset2[1].first + offset0[2].first});
        else
            offset_max = std::max(offset_max, offset0[2].first + offset2[2].first);
        ret = sum + offset_max;
    }
    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);
    std::fill(dp2, dp2+MAX_N, -1);

    printf("%lld", std::max(getDP0(1), getDP2(1)));
}

Compilation message (stderr)

beads.cpp: In function 'int main()':
beads.cpp:117:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
beads.cpp:121: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