oj.uz

Submission #45626

# Submission time Handle Problem Language Result Execution time Memory
45626 2018-04-15T16:46:22 Z evenharder Beads and wires (APIO14_beads) C++11
0 / 100
 9 ms 8196 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 8 ms 8192 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8064 KB Output is correct
6 Incorrect 9 ms 8196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 8 ms 8192 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8064 KB Output is correct
6 Incorrect 9 ms 8196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 8 ms 8192 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8064 KB Output is correct
6 Incorrect 9 ms 8196 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 8192 KB Output is correct
2 Correct 9 ms 8192 KB Output is correct
3 Correct 8 ms 8192 KB Output is correct
4 Correct 8 ms 8184 KB Output is correct
5 Correct 8 ms 8064 KB Output is correct
6 Incorrect 9 ms 8196 KB Output isn't correct
7 Halted 0 ms 0 KB -