Submission #13043

#	Time	Username	Problem	Language	Result	Execution time	Memory
13043		baneling100	Beads and wires (APIO14_beads)	C++98	0 / 100	6 ms	4992 KiB

beads

#include <stdio.h>
#include <algorithm>
#include <vector>
#define INF 0x7fffffff
#define N_MAX 200000

using namespace std;

struct rope {
    int next;
    int leng;
};
vector <rope> Rope[N_MAX+1];
int N, Check[N_MAX+1], D1[N_MAX+1], D2[N_MAX+1], D3[N_MAX+1];

void input(void) {

    int i, in1, in2, in3;

    scanf("%d",&N);
    for(i=1 ; i<N ; i++) {
        scanf("%d %d %d",&in1,&in2,&in3);
        Rope[in1].push_back({in2,in3});
        Rope[in2].push_back({in1,in3});
    }
}

void treeDP(int now) {

    int i, j=Rope[now].size(), root=-1, max1, max2, temp;

    for(i=0 ; i<j ; i++) {
        if(Check[Rope[now][i].next])
            root=i;
        else {
            Check[Rope[now][i].next]=1;
            treeDP(Rope[now][i].next);
        }
    }
    if(root>=0)
        D1[now]=Rope[now][root].leng;
    max1=max2=-INF;
    for(i=0 ; i<j ; i++)
        if(i!=root) {
            temp=max(D1[Rope[now][i].next],max(D2[Rope[now][i].next],D3[Rope[now][i].next]));
            D1[now]+=temp;
            D2[now]+=temp;
            D3[now]+=temp;
            temp=Rope[now][i].leng-temp+max(D2[Rope[now][i].next],D3[Rope[now][i].next]);
            if(max1<temp) {
                max2=max1;
                max1=temp;
            }
            else if(max2<temp)
                max2=temp;
        }
    if(max1==-INF || root==-1)
        D1[now]=0;
    else
        D1[now]+=max1;
    if(max1==-INF || max2==-INF)
        D2[now]=0;
    else
        D2[now]+=max1+max2;
}

int main(void) {

    input();
    Check[1]=1;
    treeDP(1);
    printf("%d",max(D2[1],D3[1]));

    return 0;
}

Compilation message (stderr)

beads.cpp: In function 'void input()':
beads.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&N);
     ~~~~~^~~~~~~~~
beads.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d",&in1,&in2,&in3);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

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