oj.uz

Submission #375887

# Submission time Handle Problem Language Result Execution time Memory
375887 2021-03-10T07:46:58 Z KoD Beads and wires (APIO14_beads) C++17
28 / 100
 1000 ms 748 KB 
#include <bits/stdc++.h>

template <class T>
using Vec = std::vector<T>;

template <class F>
struct RecLambda: private F {
    explicit RecLambda(F &&f): F(std::forward<F>(f)) { }
    template <class... Args>
    decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

int main() {
    int N;
    std::cin >> N;
    Vec<Vec<std::pair<int, int>>> graph(N);
    for (int i = 1; i < N; ++i) {
        int a, b, c;
        std::cin >> a >> b >> c;
        a -= 1;
        b -= 1;
        graph[a].emplace_back(b, c);
        graph[b].emplace_back(a, c);
    }
    Vec<int> t1(N), t2(N);
    const auto dfs = RecLambda([&](const auto dfs, const int u, const int p) -> void {
        Vec<int> a, b;
        for (const auto [v, c]: graph[u]) {
            if (v == p) {
                continue;
            }
            dfs(v, u);
            a.push_back(t1[v] + c);
            b.push_back(std::max(t1[v], t2[v] + c));
        }
        t1[u] = std::accumulate(b.begin(), b.end(), 0);
        t2[u] = std::numeric_limits<int>::min();
        for (int i = 0; i < (int) a.size(); ++i) {
            t2[u] = std::max(t2[u], t1[u] - b[i] + a[i]);
        }
    });
    int ans = 0;
    for (int i = 0; i < N; ++i) {
        dfs(i, -1);
        ans = std::max(ans, t1[i]);
    }
    std::cout << ans << '\n';
    return 0;
}

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 4 ms 364 KB Output is correct
17 Correct 4 ms 364 KB Output is correct
18 Correct 4 ms 364 KB Output is correct
19 Correct 3 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct

Subtask #3
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 4 ms 364 KB Output is correct
17 Correct 4 ms 364 KB Output is correct
18 Correct 4 ms 364 KB Output is correct
19 Correct 3 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Execution timed out 1091 ms 748 KB Time limit exceeded
24 Halted 0 ms 0 KB -

Subtask #4
0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 2 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 4 ms 364 KB Output is correct
17 Correct 4 ms 364 KB Output is correct
18 Correct 4 ms 364 KB Output is correct
19 Correct 3 ms 364 KB Output is correct
20 Correct 2 ms 364 KB Output is correct
21 Correct 2 ms 364 KB Output is correct
22 Correct 3 ms 364 KB Output is correct
23 Execution timed out 1091 ms 748 KB Time limit exceeded
24 Halted 0 ms 0 KB -