#397079 (C++17) No.922 東北きりきざむたん

• 問題: No.922 東北きりきざむたん
• ユーザー: Pachicobue
• 提出日時: 2019-11-09 03:41:36
• 言語: C++17 (gcc 13.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 419 ms / 2,000 ms
• コード長: 16,221 bytes
• コンパイル時間: 3,142 ms
• コンパイル使用メモリ: 223,660 KB
• 最終ジャッジ日時: 2025-01-08 03:20:45
• ジャッジサーバーID （参考情報）: judge1 / judge6

ファイルパターン	結果
sample	AC * 4
other	AC * 26

ソースコード

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

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<bool>((static_cast<u64>(mask) >> ind) & static_cast<u64>(1)); }
template<typename T> void bset(T& mask, const usize ind) { mask |= (static_cast<T>(1) << ind); }
template<typename T> void breset(T& mask, const usize ind) { mask &= ~(static_cast<T>(1) << ind); }
template<typename T> void bflip(T& mask, const usize ind) { mask ^= (static_cast<T>(1) << ind); }
template<typename T> void bset(T& mask, const usize ind, const bool b) { (b ? bset(mask, ind) : breset(mask, ind)); }
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, typename... Args>
auto read(const usize size, Args... args)
{
    std::vector<decltype(read<T>(args...))> ans(size);
    for (usize i = 0; i < size; i++) { ans[i] = read<T>(args...); }
    return ans;
}
template<typename... Types>
auto reads() { return std::tuple<std::decay_t<Types>...>{read<Types>()...}; }
#    define SHOW(...) static_cast<void>(0)
template<typename T>
T make_v(const T v) { return v; }
template<typename... Args>
auto make_v(const std::size_t size, Args... args) { return std::vector<decltype(make_v(args...))>(size, make_v(args...)); }


template<typename SemiGroup>
class sparse_table
{
public:
    using semigroup_type = SemiGroup;
    using value_type     = typename semigroup_type::value_type;
    template<typename InIt>
    sparse_table(const InIt first, const InIt last) : lg{clog(static_cast<usize>(std::distance(first, last) + 1))}, table(lg, std::vector<value_type>(1 << lg))
    {
        const usize cap = 1 << lg;
        for (usize d = 0, base = 1; d < lg; d++, base <<= 1) {
            std::copy(first, last, table[d].begin());
            for (usize b = 0; b < cap / base; b++) {
                if (b % 2 == 1) {
                    for (usize i = 1; i < base; i++) { table[d][b * base + i] = semigroup_type::merge(table[d][b * base + i - 1], table[d][b * base + i]); }
                } else {
                    for (usize i = 1; i < base; i++) { table[d][(b + 1) * base - i - 1] = semigroup_type::merge(table[d][(b + 1) * base - i - 1], table[d][(b + 1) * base - i]); }
                }
            }
        }
    }
    value_type fold(const usize l, const usize r) const
    {
        assert(l < r);
        if (r - l == 1) { return table[0][l]; }
        const usize d = log2p1(r ^ l) - 1;
        return semigroup_type::merge(table[d][l], table[d][r - 1]);
    }

private:
    const usize lg;
    std::vector<std::vector<value_type>> table;
};
template<typename Value, typename Comp = std::less<Value>, typename Bucket = uint64_t>
class linear_rmq
{
public:
    using value_type      = Value;
    using comparator_type = Comp;
    template<typename InIt>
    linear_rmq(const InIt first, const InIt last)
        : sz{static_cast<usize>(std::distance(first, last))}, bn{wind(sz + bs - 1)}, val{first, last}, bucket_val([&]() {
              std::vector<value_type> ans(bn);
              for (usize i = 0; i < sz; i++) { ans[wind(i)] = i % bs == 0 ? val[i] : std::min(ans[wind(i)], val[i], comparator_type{}); }
              return ans;
          }()),
          masks(sz, 0),
          st(bucket_val.begin(), bucket_val.end())
    {
        for (usize i = 0; i < bn; i++) {
            std::vector<usize> g(bs, sz);
            std::stack<usize> stack;
            for (usize j = 0; j < bs and ind(i, j) < sz; j++) {
                for (; not stack.empty() and not comparator_type{}(val[stack.top()], val[ind(i, j)]); stack.pop()) {}
                g[j] = stack.empty() ? sz : stack.top(), stack.push(ind(i, j));
            }
            for (usize j = 0; j < bs and ind(i, j) < sz; j++) { masks[ind(i, j)] = g[j] == sz ? static_cast<bucket_type>(0) : (masks[g[j]] | static_cast<bucket_type>(1) << (g[j] - i * bs)); }
        }
    }
    value_type fold(const usize l, const usize r) const
    {
        assert(l < r), assert(r <= sz);
        const usize lb = (l + bs - 1) / bs, rb = r / bs;
        if (lb > rb) {
            return brmq(l, r);
        } else {
            return lb < rb
                       ? (l < bs * lb
                              ? (bs * rb < r
                                     ? std::min({st.fold(lb, rb), brmq(l, bs * lb), brmq(bs * rb, r)}, comparator_type{})
                                     : std::min(st.fold(lb, rb), brmq(l, bs * lb), comparator_type{}))
                              : (bs * rb < r
                                     ? std::min(st.fold(lb, rb), brmq(bs * rb, r), comparator_type{})
                                     : st.fold(lb, rb)))
                       : (l < bs * lb
                              ? (bs * rb < r
                                     ? std::min(brmq(l, bs * lb), brmq(bs * rb, r), comparator_type{})
                                     : brmq(l, bs * lb))
                              : (bs * rb < r
                                     ? brmq(bs * rb, r)
                                     : value_type{}));
        }
    }

private:
    using bucket_type            = Bucket;
    static constexpr usize bs    = sizeof(bucket_type) * 8;
    static constexpr usize bslog = log2p1(bs) - 1;
    static constexpr usize wind(const usize n) { return n >> (bslog); }
    static constexpr usize bind(const usize n) { return bcut(n, bslog); }
    static constexpr usize ind(const usize w, const usize b) { return (w << bslog) | b; }
    value_type brmq(const usize l, usize r) const
    {
        r--;
        const Bucket w = masks[r] >> (l % bs);
        return w == 0 ? val[r] : val[l + lsbp1(w) - 1];
    }
    struct min
    {
        using value_type = Value;
        static value_type merge(const value_type& a, const value_type& b) { return std::min(a, b, comparator_type{}); }
    };

    const usize sz, bn;
    std::vector<value_type> val, bucket_val;
    std::vector<Bucket> masks;
    sparse_table<min> st;
};

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>;
template<typename Cost>
class lca
{
public:
    lca(const cost_tree<Cost>& tree, const std::size_t root = 0) : left(tree.size(), 0),
                                                                   depth([&]() {
                                                                       std::vector<std::pair<std::size_t, std::size_t>> ans;
                                                                       std::vector<bool> used(tree.size(), false);
                                                                       auto dfs = [&](auto&& self, const std::pair<std::size_t, std::size_t>& s) -> void {
                                                                           const std::size_t pos = s.second;
                                                                           used[pos] = true, left[pos] = ans.size(), ans.push_back(s);
                                                                           for (const auto& e : tree[pos]) {
                                                                               const std::size_t to = base_graph<Cost>::to(e);
                                                                               if (used[to]) { continue; }
                                                                               self(self, {s.first + 1, to}), ans.push_back(s);
                                                                           }
                                                                       };
                                                                       dfs(dfs, {0, root});
                                                                       return ans;
                                                                   }()),
                                                                   stable(depth.begin(), depth.end()) {}
    std::size_t operator()(const std::size_t u, const std::size_t v) const
    {
        const std::size_t ul = left[u], vl = left[v];
        return stable.fold(std::min(ul, vl), std::max(ul, vl) + 1).second;
    }

private:
    std::vector<std::size_t> left;
    std::vector<std::pair<std::size_t, std::size_t>> depth;
    linear_rmq<std::pair<std::size_t, std::size_t>> stable;
};

class unionfind
{
public:
    unionfind(const usize sz) : sz{sz}, rt(sz), comp_sz(sz, 1) { std::iota(rt.begin(), rt.end(), 0); }
    usize root_of(const usize a) { return assert(a < sz), rt[a] == a ? a : rt[a] = root_of(rt[a]); }
    bool unite(usize a, usize b)
    {
        assert(a < sz), assert(b < sz), a = root_of(a), b = root_of(b);
        if (a == b) { return false; }
        if (comp_sz[a] < comp_sz[b]) { std::swap(a, b); }
        return comp_sz[a] += comp_sz[b], rt[b] = a, true;
    }
    usize size_of(const usize a) { return assert(a < sz), comp_sz[root_of(a)]; }
    friend std::ostream& operator<<(std::ostream& os, const unionfind& uf)
    {
        os << "[";
        for (usize i = 0; i < uf.sz; i++) { os << uf.rt[i] << (i + 1 == uf.sz ? "" : ","); }
        return (os << "]\n");
    }

private:
    const usize sz;
    std::vector<usize> rt, comp_sz;
};
int main()
{
    auto [n, m, q] = reads<usize, usize, usize>();
    graph g(n);
    unionfind uf(n);
    for (usize i = 0; i < m; i++) {
        const auto u = read<usize>() - 1, v = read<usize>() - 1;
        uf.unite(u, v), g.add_edge(u, v, true);
    }
    using pii = std::pair<usize, usize>;
    std::vector<pii> qs;
    std::vector<usize> num(n, 0);
    for (usize i = 0; i < q; i++) {
        const auto u = read<usize>() - 1, v = read<usize>() - 1;
        qs.push_back({u, v});
        if (uf.root_of(u) != uf.root_of(v)) { num[u]++, num[v]++; }
    }
    std::vector<bool> used(n, false);
    std::vector<usize> sub(n, 0);
    std::vector<bool> isr(n, false);
    for (usize i = 0; i < n; i++) {
        if (used[i]) { continue; }
        auto dfs1 = [&](auto&& self, const usize s) -> ll {
            used[s] = true, sub[s] = num[s];
            ll dsum = 0;
            for (const usize to : g[s]) {
                if (used[to]) { continue; }
                dsum += self(self, to), dsum += sub[to], sub[s] += sub[to];
            }
            return dsum;
        };
        const ll td    = dfs1(dfs1, i);
        const usize ts = sub[i];
        pii min        = {inf_v<usize>, n};
        auto dfs2      = [&](auto&& self, const usize s, const usize p, const ll ds) -> void {
            chmin(min, {ds, s});
            for (const usize to : g[s]) {
                if (to == p) { continue; }
                const ll nds = ds - sub[to] + (ts - sub[to]);
                self(self, to, s, nds);
            }
        };
        dfs2(dfs2, i, n, td);
        isr[min.second] = true;
    }
    SHOW(isr);
    graph h(n + 1);
    for (usize i = 0; i < n; i++) {
        for (const usize to : g[i]) {
            if (i > to) { continue; }
            if (isr[i]) {
                h.add_edge(n, to, true);
            } else if (isr[to]) {
                h.add_edge(i, n, true);
            } else {
                h.add_edge(i, to, true);
            }
        }
    }
    lca lca_manager(h, n);
    std::vector<usize> depth(n + 1, 0);
    auto dfs = [&](auto&& self, const usize s, const usize p) -> void {
        for (const usize to : h[s]) {
            if (to == p) { continue; }
            depth[to] = depth[s] + 1, self(self, to, s);
        }
    };
    dfs(dfs, n, n + 1);
    ll ans = 0;
    for (const auto& q : qs) {
        const auto [u, v] = q;
        const usize l     = lca_manager(u, v);
        ans += depth[u] + depth[v] - 2LL * depth[l];
    }
    std::cout << ans << std::endl;
    return 0;
}