Submission #552627

#	Time	Username	Problem	Language	Result	Execution time	Memory
552627		tht2005	Beads and wires (APIO14_beads)	C++17	0 / 100	4 ms	5012 KiB

beads

#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 (stderr)

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
• Subtask 2: 0 / 15
• Subtask 3: 0 / 29
• Subtask 4: 0 / 43