oj.uz

Submission #580878

# Submission time Handle Problem Language Result Execution time Memory
580878 2022-06-22T04:59:19 Z 박상훈(#8359) Beads and wires (APIO14_beads) C++17
0 / 100
 3 ms 5004 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){
    vector<int> C;
    for (auto &[v, w]:adj[s]) if (v!=pa){
        dfs(v, s, w);
        C.push_back(dp[v][0] + w - dp[v][1]);
        dp[s][0] += dp[v][1];
        dp[s][1] += dp[v][1];
    }
    sort(C.begin(), C.end(), greater<int>());

    for (int i=0;i+1<(int)C.size();i+=2){
        if (i==2) break;
        if (C[i] + C[i+1] < 0) break;
        dp[s][0] += C[i] + C[i+1];
    }

    if (C.empty()) return;
    dp[s][1] += w0 + C[0];
    dp[s][1] = max(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);
    }
    dfs(1);
    printf("%d\n", dp[1][0]);
    return 0;
}

Compilation message

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

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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