oj.uz

Submission #697737

# Submission time Handle Problem Language Result Execution time Memory
697737 2023-02-11T01:44:12 Z WHC_MIK_7521X Beads and wires (APIO14_beads) C++17
0 / 100
 2 ms 3412 KB 
#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;
}

Compilation message

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

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3380 KB Output is correct
2 Correct 2 ms 3384 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3384 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3380 KB Output is correct
2 Correct 2 ms 3384 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3384 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3380 KB Output is correct
2 Correct 2 ms 3384 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3384 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3380 KB Output is correct
2 Correct 2 ms 3384 KB Output is correct
3 Correct 2 ms 3412 KB Output is correct
4 Correct 2 ms 3384 KB Output is correct
5 Correct 2 ms 3412 KB Output is correct
6 Incorrect 2 ms 3412 KB Output isn't correct
7 Halted 0 ms 0 KB -