結果

問題 No.912 赤黒木
ユーザー PachicobuePachicobue
提出日時 2019-10-19 01:37:38
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 7,127 bytes
コンパイル時間 2,638 ms
コンパイル使用メモリ 213,444 KB
実行使用メモリ 123,776 KB
最終ジャッジ日時 2024-06-25 23:08:35
合計ジャッジ時間 21,332 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 2 ms
5,376 KB
testcase_02 WA -
testcase_03 AC 4 ms
5,376 KB
testcase_04 WA -
testcase_05 WA -
testcase_06 WA -
testcase_07 WA -
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 WA -
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 WA -
testcase_22 AC 713 ms
93,608 KB
testcase_23 AC 706 ms
93,712 KB
testcase_24 AC 719 ms
93,712 KB
testcase_25 AC 884 ms
88,832 KB
testcase_26 AC 905 ms
91,520 KB
testcase_27 AC 854 ms
87,424 KB
testcase_28 AC 899 ms
123,776 KB
testcase_29 AC 895 ms
123,136 KB
testcase_30 WA -
testcase_31 WA -
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#pragma GCC diagnostic ignored "-Wsign-compare"
#pragma GCC diagnostic ignored "-Wsign-conversion"

#define NDEBUG
using i32 = int32_t;
using i64 = int64_t;
using u32 = uint32_t;
using u64 = uint64_t;
using uint = unsigned int;
using usize = std::size_t;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
template<typename T> constexpr T popcount(const T u) { return u ? static_cast<T>(__builtin_popcountll(static_cast<u64>(u))) : static_cast<T>(0); }
template<typename T> constexpr T log2p1(const T u) { return u ? static_cast<T>(64 - __builtin_clzll(static_cast<u64>(u))) : static_cast<T>(0); }
template<typename T> constexpr T msbp1(const T u) { return log2p1(u); }
template<typename T> constexpr T lsbp1(const T u) { return __builtin_ffsll(u); }
template<typename T> constexpr T clog(const T u) { return u ? log2p1(u - 1) : static_cast<T>(u); }
template<typename T> constexpr bool ispow2(const T u) { return u and (static_cast<u64>(u) & static_cast<u64>(u - 1)) == 0; }
template<typename T> constexpr T ceil2(const T u) { return static_cast<T>(1) << clog(u); }
template<typename T> constexpr T floor2(const T u) { return u == 0 ? static_cast<T>(0) : static_cast<T>(1) << (log2p1(u) - 1); }
template<typename T> constexpr bool btest(const T mask, const usize ind) { return ((static_cast<u64>(mask) >> ind) & static_cast<u64>(1)); }
template<typename T> constexpr T bcut(const T mask, const usize ind) { return ind == 0 ? static_cast<T>(0) : static_cast<T>((static_cast<u64>(mask) << (64 - ind)) >> (64 - ind)); }
template<typename T> bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }
template<typename T> bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }
constexpr unsigned int mod                  = 1000000007;
template<typename T> constexpr T inf_v      = std::numeric_limits<T>::max() / 4;
template<typename Real> constexpr Real pi_v = Real{3.141592653589793238462643383279502884};
template<typename T>
T read()
{
    T v;
    return std::cin >> v, v;
}
template<typename T>
std::vector<T> read_vec(const std::size_t size)
{
    std::vector<T> v(size);
    for (auto& e : v) { std::cin >> e; }
    return v;
}
template<typename... Types>
auto read_vals() { return std::tuple<std::decay_t<Types>...>{read<Types>()...}; }
#define SHOW(...) static_cast<void>(0)
template<typename T>
std::vector<T> make_v(const std::size_t size, T v) { return std::vector<T>(size, v); }
template<class... Args>
auto make_v(const std::size_t size, Args... args) { return std::vector<decltype(make_v(args...))>(size, make_v(args...)); }

template<typename Cost>
class base_graph
{
public:
    using cost_type = Cost;
    base_graph(const usize sz) : sz{sz}, edges(sz), rev_edges(sz) {}
    void add_edge(const usize from, const usize to, const Cost cost, const bool bi = false)
    {
        assert(from < sz), assert(to < sz);
        edges[from].push_back(edge{from, to, cost}), rev_edges[to].push_back(edge(to, from, cost));
        if (bi) { add_edge(to, from, cost, false); }
    }
    struct edge
    {
        edge(const usize from, const usize to, const Cost cost) : from{from}, to{to}, cost{cost} {}
        usize from, to;
        Cost cost;
        bool operator<(const edge& e) const { return cost != e.cost ? cost < e.cost : to < e.to; }
    };
    std::vector<edge>& operator[](const usize i) { return assert(i < sz), edges[i]; }
    const std::vector<edge>& operator[](const usize i) const { return assert(i < sz), edges[i]; }
    const std::vector<std::vector<edge>>& rev_edge() const { return rev_edges; }
    std::vector<std::vector<edge>>& rev_edge() { return rev_edges; }
    friend std::ostream& operator<<(std::ostream& os, const base_graph& g)
    {
        os << "[\n";
        for (usize i = 0; i < g.sz; i++) {
            for (const auto& e : g.edges[i]) { os << i << "->" << e.to << ":" << e.cost << "\n"; }
        }
        return (os << "]\n");
    }
    static usize to(const edge& e) { return e.to; }
    usize size() const { return sz; }

private:
    const usize sz;
    std::vector<std::vector<edge>> edges, rev_edges;
};
template<>
class base_graph<void>
{
public:
    base_graph(const usize sz) : sz{sz}, edges(sz), rev_edges(sz) {}
    void add_edge(const usize from, const usize to, const bool bi = false)
    {
        assert(from < sz), assert(to < sz);
        edges[from].push_back(to), rev_edges[to].push_back(from);
        if (bi) { add_edge(to, from, false); }
    }
    std::vector<usize>& operator[](const usize i) { return assert(i < sz), edges[i]; }
    const std::vector<usize>& operator[](const usize i) const { return assert(i < sz), edges[i]; }
    const std::vector<std::vector<usize>>& rev_edge() const { return rev_edges; }
    std::vector<std::vector<usize>>& rev_edge() { return rev_edges; }
    friend std::ostream& operator<<(std::ostream& os, const base_graph& g)
    {
        os << "[\n";
        for (usize i = 0; i < g.sz; i++) {
            for (const usize to : g.edges[i]) { os << i << "->" << to << "\n"; }
        }
        return (os << "]\n");
    }
    static usize to(const usize e) { return e; }
    usize size() const { return sz; }

private:
    const usize sz;
    std::vector<std::vector<usize>> edges, rev_edges;
};
using graph = base_graph<void>;
using tree  = graph;
template<typename Cost>
using cost_graph = base_graph<Cost>;
template<typename Cost>
using cost_tree = cost_graph<Cost>;
int main()
{
    const auto n = read<usize>();
    graph b(n), r(n);
    std::vector<usize> dim(n, 0);
    for (usize i = 0; i < n - 1; i++) {
        const auto u = read<usize>() - 1, v = read<usize>() - 1;
        b.add_edge(u, v, true), (dim[u] += 1) %= 2, (dim[v] += 1) %= 2;
    }
    for (usize i = 0; i < n - 1; i++) {
        const auto u = read<usize>() - 1, v = read<usize>() - 1;
        r.add_edge(u, v, true);
    }
    auto dp = make_v(n, 3, 2, inf_v<usize>);
    for (usize i = 0; i < n; i++) { dp[i][0][dim[i]] = 0; }
    auto dfs = [&](auto&& self, const usize s, const usize p) -> void {
        for (const usize to : r[s]) {
            if (to == p) { continue; }
            self(self, to, s);
            auto tmp = make_v(3, 2, inf_v<usize>);
            for (usize p = 0; p < 2; p++) {          // sのparity
                for (usize cp = 0; cp < 2; cp++) {   // 子のparity
                    for (usize e = 0; e < 2; e++) {  // 赤辺を加えるか
                        const bool ncp = cp ^ e, np = p ^ e;
                        for (usize n = 0; n < 3; n++) {         // sのoddの数
                            for (usize cn = 0; cn < 3; cn++) {  // 子のoddの数
                                const usize nn = n + cn + ncp;
                                if (nn >= 3) { continue; }
                                chmin(tmp[nn][np], dp[s][n][p] + dp[to][cn][cp] + e);
                            }
                        }
                    }
                }
            }
            dp[s] = tmp;
        }
    };
    dfs(dfs, 0, n);
    std::cout << n - 1 + std::min(dp[0][2][0], dp[0][1][1]) << std::endl;
    return 0;
}
0