oj.uz

Submission #581020

# Submission time Handle Problem Language Result Execution time Memory
581020 2022-06-22T08:23:43 Z 박상훈(#8359) Beads and wires (APIO14_beads) C++17
0 / 100
 3 ms 4948 KB 
#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
vector<pair<int, int>> adj[200200];
int dp[200200][2];

void dfs(int s, int pa = -1, int w0 = 0){
    int tmp = -1e9;
    dp[s][0] = 0;
    for (auto &[v, w]:adj[s]) if (v!=pa){
        dfs(v, s, w);
        tmp = max(tmp, dp[v][0] + w - dp[v][1]);
        dp[s][0] += dp[v][1];
    }

    if (w0+tmp>0) dp[s][1] = dp[s][0] + w0 + tmp;
    else dp[s][1] = dp[s][0];
    //if (C.size()>=2) dp[s][0] = max(dp[s][0], dp[s][0] + C[0] + C[1]);

    //printf("%d: %d %d\n", s, dp[s][0], dp[s][1]);
}

int main(){
    int n;
    scanf("%d", &n);
    for (int i=0;i<n-1;i++){
        int x, y, z;
        scanf("%d %d %d", &x, &y, &z);
        adj[x].emplace_back(y, z);
        adj[y].emplace_back(x, z);
    }
    vector<int> D;
    for (int i=1;i<=n;i++) if (adj[i].size()==1) {D.push_back(i); break;}
    int ans = 0;
    for (auto i:D){
        dfs(i);
        ans = max(ans, dp[i][0]);
    }
    printf("%d\n", ans);
    return 0;
}

Compilation message

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

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 4948 KB Output isn't correct
2 Halted 0 ms 0 KB -