Submission #393937

#	Time	Username	Problem	Language	Result	Execution time	Memory
393937		KoD	Duathlon (APIO18_duathlon)	C++17	100 / 100	141 ms	30492 KiB

count_triplets

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept : itr(pos) {}
        constexpr void operator++() noexcept { ++itr; }
        constexpr bool operator!=(const Iter& other) const noexcept {
            return itr != other.itr;
        }
        constexpr usize operator*() const noexcept { return itr; }
    };
    const Iter first, last;

  public:
    explicit constexpr rep(const usize first, const usize last) noexcept
        : first(first), last(std::max(first, last)) {}
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

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

template <class G> explicit RecLambda(G&&) -> RecLambda<std::decay_t<G>>;

template <class T> bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

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

void APIO18A_main() {
    usize N, M;
    std::cin >> N >> M;
    Vec<Vec<usize>> graph(N);
    while (M--) {
        usize a, b;
        std::cin >> a >> b;
        a -= 1;
        b -= 1;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    Vec<Vec<usize>> bctree(N);
    const auto add_node = [&] {
        const auto ret = bctree.size();
        bctree.push_back({});
        return ret;
    };
    Vec<usize> depth(N), ord(N), low(N);
    usize time = 0;
    std::stack<usize> store;
    const auto dfs = RecLambda(
        [&](auto&& dfs, const usize u, const usize p, const usize d) -> void {
            depth[u] = d;
            ord[u] = low[u] = time;
            time += 1;
            store.push(u);
            for (const auto v : graph[u])
                if (v != p) {
                    if (depth[v] == 0) {
                        dfs(v, u, d + 1);
                        if (ord[u] <= low[v]) {
                            const auto node = add_node();
                            bctree[u].push_back(node);
                            while (bctree[node].empty() or
                                   bctree[node].back() != v) {
                                bctree[node].push_back(store.top());
                                store.pop();
                            }
                        }
                        setmin(low[u], low[v]);
                    } else {
                        setmin(low[u], ord[v]);
                    }
                }
        });
    Vec<usize> roots;
    for (const auto root : rep(0, N)) {
        if (depth[root] == 0) {
            dfs(root, root, 1);
            roots.push_back(root);
        }
    }
    Vec<usize> subtree(bctree.size());
    u64 ans = 0;
    usize whole = 0;
    const auto calc = RecLambda([&](auto&& dfs, const usize u) -> void {
        subtree[u] = (u < N);
        for (const auto v : bctree[u]) {
            dfs(v);
            subtree[u] += subtree[v];
            if (u >= N) {
                ans -= (u64)bctree[u].size() * subtree[v] * (subtree[v] - 1);
            }
        }
    });
    const auto flush = RecLambda([&](auto&& dfs, const usize u) -> void {
        if (u >= N) {
            ans -= (u64)bctree[u].size() * (whole - subtree[u]) *
                   (whole - subtree[u] - 1);
        }
        for (const auto v : bctree[u]) {
            dfs(v);
        }
    });
    for (const auto root : roots) {
        calc(root);
        whole = subtree[root];
        ans += (u64)whole * (whole - 1) * (whole - 2);
        flush(root);
    }
    std::cout << ans << '\n';
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    APIO18A_main();
    return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 8 / 8
• Subtask 4: 10 / 10
• Subtask 5: 13 / 13
• Subtask 6: 15 / 15
• Subtask 7: 20 / 20
• Subtask 8: 8 / 8
• Subtask 9: 10 / 10