oj.uz

Submission #569475

# Submission time Handle Problem Language Result Execution time Memory
569475 2022-05-27T12:17:10 Z Forested Beads and wires (APIO14_beads) C++17
100 / 100
 236 ms 34680 KB 
#ifndef LOCAL
#define FAST_IO
#endif

// ===== template.hpp =====
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cmath>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

#define OVERRIDE(a, b, c, d, ...) d
#define REP2(i, n) for (i32 i = 0; i < (i32) (n); ++i)
#define REP3(i, m, n) for (i32 i = (i32) (m); i < (i32) (n); ++i)
#define REP(...) OVERRIDE(__VA_ARGS__, REP3, REP2)(__VA_ARGS__)
#define PER(i, n) for (i32 i = (i32) (n) - 1; i >= 0; --i)
#define ALL(x) begin(x), end(x)

using namespace std;

using u32 = unsigned int;
using u64 = unsigned long long;
using u128 = __uint128_t;
using i32 = signed int;
using i64 = signed long long;
using i128 = __int128_t;
using f64 = double;
using f80 = long double;

template <typename T>
using Vec = vector<T>;

template <typename T>
bool chmin(T &x, const T &y) {
    if (x > y) {
        x = y;
        return true;
    }
    return false;
}
template <typename T>
bool chmax(T &x, const T &y) {
    if (x < y) {
        x = y;
        return true;
    }
    return false;
}

istream &operator>>(istream &is, i128 &x) {
    i64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, i128 x) {
    os << (i64) x;
    return os;
}
istream &operator>>(istream &is, u128 &x) {
    u64 v;
    is >> v;
    x = v;
    return is;
}
ostream &operator<<(ostream &os, u128 x) {
    os << (u64) x;
    return os;
}

template <typename F, typename Comp = less<>>
Vec<i32> sort_index(i32 n, F f, Comp comp = Comp()) {
    Vec<i32> idx(n);
    iota(ALL(idx), 0);
    sort(ALL(idx), [&](i32 i, i32 j) -> bool {
        return comp(f(i), f(j));
    });
    return idx;
}

[[maybe_unused]] constexpr i32 INF = 1000000100;
[[maybe_unused]] constexpr i64 INF64 = 3000000000000000100;

#ifdef FAST_IO
struct FastIO {
    FastIO() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout << fixed << setprecision(10);
    }
} fast_io;
#endif
// ===== template.hpp =====

#ifdef DEBUGF
#include "cpl/template/debug.hpp"
#else
#define DBG(x) (void) 0
#endif

// ===== graph.hpp =====

#include <utility>
#include <vector>
#include <numeric>
#include <cassert>

template <typename Edge>
class Graph {
    std::vector<std::vector<Edge>> edges;

public:
    Graph() : edges() {}
    Graph(int v) : edges(v) {
        assert(v >= 0);
    }
    
    std::vector<int> add_vertices(int n) {
        int v = (int) edges.size();
        std::vector<int> idx(n);
        std::iota(idx.begin(), idx.end(), v);
        edges.resize(edges.size() + n);
        return idx;
    }

    template <typename... T>
    void add_directed_edge(int from, int to, T &&...val) {
        assert(from >= 0 && from < (int) edges.size());
        assert(to >= 0 && to < (int) edges.size());
        edges[from].emplace_back(Edge(to, std::forward<T>(val)...));
    }

    template <typename... T>
    void add_undirected_edge(int u, int v, const T &...val) {
        assert(u >= 0 && u < (int) edges.size());
        assert(v >= 0 && v < (int) edges.size());
        edges[u].emplace_back(Edge(v, val...));
        edges[v].emplace_back(Edge(u, val...));
    }

    int size() const {
        return (int) edges.size();
    }

    const std::vector<Edge> &operator[](int v) const {
        assert(v >= 0 && v < (int) edges.size());
        return edges[v];
    }

    std::vector<Edge> &operator[](int v) {
        assert(v >= 0 && v < (int) edges.size());
        return edges[v];
    }
};

struct UnweightedEdge {
    int to;

    UnweightedEdge(int t) : to(t) {}
    
    explicit operator int() const {
        return to;
    }

    using Weight = std::size_t;
    Weight weight() const {
        return 1;
    }
};

template <typename T>
struct WeightedEdge {
    int to;
    T wt;

    WeightedEdge(int t, const T &w) : to(t), wt(w) {}

    explicit operator int() const {
        return to;
    }

    using Weight = T;
    Weight weight() const {
        return wt;
    }
};

// ===== graph.hpp =====
// ===== rerooting.hpp =====

#include <optional>
#include <queue>
#include <utility>
#include <vector>

template <typename G, typename T, typename Apply, typename Merge>
T rerooting_sub1(
    const G &g,
    const T &id,
    const Apply &ap,
    const Merge &me,
    int v,
    int p,
    std::vector<std::vector<std::optional<T>>> &dp) {
    T acc = id;
    for (int i = 0; i < (int) g[v].size(); ++i) {
        if ((int) g[v][i] != p) {
            T val = rerooting_sub1(g, id, ap, me, (int) g[v][i], v, dp);
            dp[v][i] = ap(val, v, g[v][i]);
            acc = me(acc, *dp[v][i]);
        }
    }
    return acc;
}

template <typename G, typename T, typename Apply, typename Merge>
void rerooting_sub2(
    const G &g,
    const T &id,
    const Apply &ap,
    const Merge &me,
    int root,
    std::vector<std::vector<std::optional<T>>> &dp) {
    std::queue<std::pair<int, T>> que;
    que.emplace(root, id);
    while (!que.empty()) {
        auto [v, val] = que.front();
        que.pop();
        std::vector<T> acc_l(g[v].size() + 1);
        acc_l[0] = id;
        int emp_idx = -1;
        for (int i = 0; i < (int) g[v].size(); ++i) {
            if (!(bool) dp[v][i]) {
                dp[v][i] = ap(val, v, g[v][i]);
                emp_idx = i;
            }
            acc_l[i + 1] = me(acc_l[i], *dp[v][i]);
        }
        T acc_r = id;
        for (int i = (int) g[v].size() - 1; i >= 0; --i) {
            if (i != emp_idx) {
                que.emplace((int) g[v][i], me(acc_l[i], acc_r));
            }
            acc_r = me(*dp[v][i], acc_r);
        }
    }
}

// Apply: Fn(T, int, E) -> T
// Merge: Fn(T, T) -> T
template <typename G, typename T, typename Apply, typename Merge>
std::vector<T>
rerooting(const G &g, const T &id, const Apply &ap, const Merge &me) {
    std::vector<std::vector<std::optional<T>>> dp(g.size());
    for (int i = 0; i < (int) g.size(); ++i) {
        dp[i].resize(g[i].size(), std::nullopt);
    }
    rerooting_sub1(g, id, ap, me, 0, 0, dp);
    rerooting_sub2(g, id, ap, me, 0, dp);
    std::vector<T> buf(g.size(), id);
    for (int i = 0; i < (int) g.size(); ++i) {
        for (std::optional<T> &val : dp[i]) {
            buf[i] = me(buf[i], std::move(*val));
        }
    }
    return buf;
}

template <typename G, typename T, typename Apply, typename Merge>
std::vector<std::vector<T>>
rerooting_raw(const G &g, const T &id, const Apply &ap, const Merge &me) {
    std::vector<std::vector<std::optional<T>>> dp(g.size());
    for (int i = 0; i < (int) g.size(); ++i) {
        dp[i].resize(g[i].size(), std::nullopt);
    }
    rerooting_sub1(g, id, ap, me, 0, 0, dp);
    rerooting_sub2(g, id, ap, me, 0, dp);
    std::vector<std::vector<T>> buf(g.size());
    for (int i = 0; i < (int) g.size(); ++i) {
        buf[i].reserve(g[i].size());
        for (const std::optional<T> &val : dp[i]) {
            buf[i].emplace_back(*val);
        }
    }
    return buf;
}
// ===== rerooting.hpp =====

struct State {
    i32 middle;
    i32 top;
    State() : middle(-INF), top(0) {}
    State(i32 m, i32 t) : middle(m), top(t) {}
};

int main() {
    i32 n;
    cin >> n;
    Graph<WeightedEdge<i32>> g(n);
    REP(i, n - 1) {
        i32 a, b, c;
        cin >> a >> b >> c;
        --a;
        --b;
        g.add_undirected_edge(a, b, c);
    }
    
    const auto ap = [](State state, i32, const WeightedEdge<i32> &e) -> State {
        return State(state.top + e.wt, max(state.middle + e.wt, state.top));
    };
    const auto me = [](State x, State y) -> State {
        return State(max(x.middle + y.top, x.top + y.middle), x.top + y.top);
    };
    State id;
    Vec<State> res = rerooting(g, id, ap, me);
    i32 ans = 0;
    REP(i, n) {
        chmax(ans, res[i].top);
    }
    cout << ans << '\n';
}

Subtask #1
13.0 / 13.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 3 ms 1052 KB Output is correct
24 Correct 4 ms 980 KB Output is correct
25 Correct 4 ms 980 KB Output is correct
26 Correct 9 ms 1788 KB Output is correct
27 Correct 6 ms 1748 KB Output is correct
28 Correct 5 ms 2032 KB Output is correct
29 Correct 5 ms 1876 KB Output is correct
30 Correct 6 ms 1864 KB Output is correct
31 Correct 7 ms 2132 KB Output is correct

Subtask #4
43.0 / 43.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 0 ms 320 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 320 KB Output is correct
13 Correct 1 ms 212 KB Output is correct
14 Correct 1 ms 324 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 320 KB Output is correct
23 Correct 3 ms 1052 KB Output is correct
24 Correct 4 ms 980 KB Output is correct
25 Correct 4 ms 980 KB Output is correct
26 Correct 9 ms 1788 KB Output is correct
27 Correct 6 ms 1748 KB Output is correct
28 Correct 5 ms 2032 KB Output is correct
29 Correct 5 ms 1876 KB Output is correct
30 Correct 6 ms 1864 KB Output is correct
31 Correct 7 ms 2132 KB Output is correct
32 Correct 37 ms 7612 KB Output is correct
33 Correct 31 ms 7620 KB Output is correct
34 Correct 31 ms 7628 KB Output is correct
35 Correct 216 ms 30304 KB Output is correct
36 Correct 236 ms 30264 KB Output is correct
37 Correct 210 ms 30176 KB Output is correct
38 Correct 162 ms 33320 KB Output is correct
39 Correct 173 ms 31764 KB Output is correct
40 Correct 152 ms 32704 KB Output is correct
41 Correct 218 ms 34680 KB Output is correct