Submission #34708

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

beads

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

int dp[200005][2][2];

int 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;
    }
    int sum = 0;
    for(int i=0;i<E[u].size();++i){
        int v = E[u][i].first;
        if(v == pre)
            continue;
        int 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;

    int mx1,mx2;
    mx1 = mx2 = 0;
    for(int i=0;i<E[u].size();++i){
        int v = E[u][i].first;
        if(v == pre)
            continue;
        int w = E[u][i].second;
        int del = max( recur(v,0,0,u) , max(recur(v,1,0,u) , recur(v,1,1,u)+w*(E[v].size() > 1) ) );
        int add = max( recur(v,0,0,u) , recur(v,1,0,u) ) + w;
        int 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,w;
        scanf("%d%d%d",&u,&v,&w);
        E[u].push_back({v,w});
        E[v].push_back({u,w});
    }
    E[1].push_back({0,0});
    printf("%d\n",max(recur(1,0,0,0) , recur(1,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

3
1 2 10
2 3 50


*/

Compilation message (stderr)

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

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