제출 #697737

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
697737		WHC_MIK_7521X	구슬과 끈 (APIO14_beads)	C++17	0 / 100	2 ms	3412 KiB

beads

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int n,dp[N][2][2];
struct edge{
    int w,to,nxt;
};
edge ed[N<<1];
int cnt,h[N];
void add(int st,int et,int wi){
    cnt++;
    ed[cnt].to=et;
    ed[cnt].w=wi;
    ed[cnt].nxt=h[st];
    h[st]=cnt;
}
void dfs(int x,int fa){
    dp[x][0][0]=0;
    for(int i=h[x];i;i=ed[i].nxt){
        int v=ed[i].to;
        if(v==fa)continue;
        dfs(v,x);
        int t0=max(dp[v][0][0],dp[v][1][0]),t1=dp[v][1][1];
        int dp00=max({dp[x][0][0]+t0,dp[x][0][0]+t1+ed[i].w}),
        dp10=max({dp[x][1][1]+t0+ed[i].w,dp[x][1][0]+t1+ed[i].w,dp[x][1][0]+t0}),
        dp11=max({dp[x][1][1]+t0,dp[x][1][1]+t1+ed[i].w,dp[x][0][0]+t0+ed[i].w});
        dp[x][0][0]=dp00;
        dp[x][1][0]=dp10;
        dp[x][1][1]=dp11;
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1,x,y,w;i<n;i++){
        scanf("%d%d%d",&x,&y,&w);
        add(x,y,w);
        add(y,x,w);
    }
    memset(dp,-63,sizeof dp);
    dfs(1,0);
    printf("%d",max(dp[1][0][0],dp[1][1][0]));
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

beads.cpp: In function 'int main()':
beads.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   33 |     scanf("%d",&n);
      |     ~~~~~^~~~~~~~~
beads.cpp:35:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   35 |         scanf("%d%d%d",&x,&y,&w);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~

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