oj.uz

Submission #552627

# Submission time Handle Problem Language Result Execution time Memory
552627 2022-04-23T12:44:10 Z tht2005 Beads and wires (APIO14_beads) C++17
0 / 100
 4 ms 5012 KB 
#include <bits/stdc++.h>

using namespace std;

const int NINF = numeric_limits<int>::min();

const int N = 200005;
int n, f[N][3], aux[3];
vector<pair<int, int>> aj[N];

void dfs(int v, int p_) {
    f[v][0] = 0;
    f[v][1] = f[v][2] = NINF;
    for(const auto& [w, u] : aj[v]) {
        if(u == p_) continue;
        dfs(u, v);
        for(int i = 0; i < 3; ++i) {
            aux[i] = f[v][i];
            f[v][i] = NINF;
        }
        for(int i = 0; i < 3; ++i) {
            if(aux[i] != NINF) {
                f[v][i] = aux[i] + max(max(f[u][0], f[u][2]), w + f[u][1]);
            }
        }
        for(int i = 0; i < 2; ++i) {
            if(aux[i] != NINF) {
                f[v][i + 1] = max(f[v][i + 1], aux[i] + w + max(f[u][0], f[u][2]));
            }
        }
    }
}

int main() {
    scanf("%d", &n);
    for(int _ = 1; _ < n; ++_) {
        int u, v, w;
        scanf("%d %d %d", &u, &v, &w);
        aj[u].emplace_back(w, v);
        aj[v].emplace_back(w, u);
    }
    dfs(1, -1);
    printf("%d", max(f[1][0], f[1][2]));
    return 0;
}

Compilation message

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

Subtask #1
0 / 13.0

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

Subtask #2
0 / 15.0

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

Subtask #3
0 / 29.0

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

Subtask #4
0 / 43.0

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