Submission #34714

#	Time	Username	Problem	Language	Result	Execution time	Memory
34714		oOZinzOo	Beads and wires (APIO14_beads)	C++11	0 / 100	11 ms	11264 KiB

beads

#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstring>
using namespace std;
int alln;
vector <pair<int,long long> > E[200005];

long long dp[200005][2][2];

long long recur(int u,int ins,int wp,int pre){
    if(dp[u][ins][wp] >= 0)
        return dp[u][ins][wp];
    if(ins == 1){
        if(wp == 0 && E[u].size() <= 2)
            return dp[u][ins][wp] = 0;
        else if(wp == 1 && E[u].size() <= 1)
            return dp[u][ins][wp] = 0;
    }
    long long sum = 0;
    for(int i=0;i<E[u].size();++i){
        int v = E[u][i].first;
        if(v == pre)
            continue;
        long long w = E[u][i].second;
        sum += max( recur(v,0,0,u) , max(recur(v,1,0,u) , recur(v,1,1,u)+w*(E[v].size() > 1) ) );
    }

    if(ins == 0)
        return dp[u][ins][wp] = sum;

    long long mx1,mx2;
    mx1 = mx2 = 0;
    for(int i=0;i<E[u].size();++i){
        int v = E[u][i].first;
        if(v == pre)
            continue;
        long long w = E[u][i].second;
        long long del = max( recur(v,0,0,u) , max(recur(v,1,0,u) , recur(v,1,1,u)+w*(E[v].size() > 1) ) );
        long long add = recur(v,0,0,u) + w;
        long long now = sum-del+add;
        if( mx1 < now )
            mx2 = mx1 , mx1 = now;
        else if(mx2 < now)
            mx2 = now;
    }
    if(wp == 1)
        return dp[u][ins][wp] = mx1;
    return dp[u][ins][wp] = sum+(mx1-sum)+(mx2-sum);

}

int main()
{
    memset(dp,-1,sizeof(dp));
    scanf("%d",&alln);
    for(int i=1;i<alln;++i){
        int u,v;
        long long w;
        scanf("%d%d%lld",&u,&v,&w);
        E[u].push_back({v,w});
        E[v].push_back({u,w});
    }
    int root = 5;
    E[root].push_back({0,0});
    printf("%lld\n",max(recur(root,0,0,0) , recur(root,1,0,0) ) );

    return 0;
}

/**
5
1 2 10
1 3 40
1 4 15
1 5 20

10
4 10 2
1 2 21
1 3 13
6 7 1
7 9 5
2 4 3
2 5 8
1 6 55
6 8 34

6
1 2 15
2 3 35
3 4 20
4 5 30
5 6 25


*/

Compilation message (stderr)

beads.cpp: In function 'long long int recur(int, int, int, int)':
beads.cpp:21:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<E[u].size();++i){
                 ~^~~~~~~~~~~~
beads.cpp:34:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=0;i<E[u].size();++i){
                 ~^~~~~~~~~~~~
beads.cpp: In function 'int main()':
beads.cpp:56:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&alln);
     ~~~~~^~~~~~~~~~~~
beads.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d%lld",&u,&v,&w);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~

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