# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
13043 | baneling100 | 구슬과 끈 (APIO14_beads) | C++98 | 6 ms | 4992 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |