oj.uz

답안 #13043

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
13043 2015-01-27T09:21:02 Z baneling100 구슬과 끈 (APIO14_beads) C++
0 / 100
 6 ms 4992 KB 
#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

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

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4992 KB Output is correct
2 Correct 5 ms 4992 KB Output is correct
3 Correct 5 ms 4992 KB Output is correct
4 Correct 6 ms 4992 KB Output is correct
5 Correct 5 ms 4992 KB Output is correct
6 Incorrect 5 ms 4992 KB Output isn't correct
7 Halted 0 ms 0 KB -