Submission #13044

#	Time	Username	Problem	Language	Result	Execution time	Memory
13044		baneling100	Beads and wires (APIO14_beads)	C++98	100 / 100	236 ms	22556 KiB

beads

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

using namespace std;

struct rope {
    int next;
    int cost;
};
vector <rope> Rope[N_MAX+1];
int N, Check[N_MAX+1], D1[N_MAX+1], D2[N_MAX+1], D3[N_MAX+1], D4[N_MAX+1], D5[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();
    int anc=-1, temp, max1, max2, max3, max4, max5, j1=-1, j2=-1;

    for(i=0 ; i<j ; i++) {
        if(Check[Rope[now][i].next])
            anc=i;
        else {
            Check[Rope[now][i].next]=1;
            treeDP(Rope[now][i].next);
        }
    }
    if(anc>=0)
        D1[now]=D4[now]=Rope[now][anc].cost;
    max1=max2=max3=max4=max5=-INF;
    for(i=0 ; i<j ; i++) {
        if(i!=anc) {
            temp=max(D4[Rope[now][i].next],D5[Rope[now][i].next]);
            D1[now]+=temp;
            D2[now]+=temp;
            D3[now]+=temp;
            D4[now]+=temp;
            D5[now]+=temp;
            if(max1<Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp) {
                max3=max1;
                max1=Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp;
                j1=i;
            }
            else if(max3<Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp)
                max3=Rope[now][i].cost+max(D2[Rope[now][i].next],D3[Rope[now][i].next])-temp;
            if(max2<Rope[now][i].cost+D5[Rope[now][i].next]-temp) {
                max4=max2;
                max2=Rope[now][i].cost+D5[Rope[now][i].next]-temp;
                j2=i;
            }
            else if(max4<Rope[now][i].cost+D5[Rope[now][i].next]-temp)
                max4=Rope[now][i].cost+D5[Rope[now][i].next]-temp;
            if(max5<max(D1[Rope[now][i].next],max(D2[Rope[now][i].next],D3[Rope[now][i].next]))-temp)
                max5=max(D1[Rope[now][i].next],max(D2[Rope[now][i].next],D3[Rope[now][i].next]))-temp;
        }
    }
    if(anc==-1 || j<=1)
        D1[now]=0;
    else
        D1[now]+=max1;
    if((anc==-1 && j<=1) || (anc>=0 && j<=2))
        D2[now]=0;
    else {
        if(j1==j2)
            D2[now]+=max(max1+max4,max2+max3);
        else
            D2[now]+=max1+max2;
    }
    if((anc==-1 && j==0) || (anc>=0 && j<=1))
        D3[now]=0;
    else
        D3[now]+=max5;
    if(anc==-1 || j<=1)
        D4[now]=0;
    else
        D4[now]+=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: 13 / 13
• Subtask 2: 15 / 15
• Subtask 3: 29 / 29
• Subtask 4: 43 / 43