結果

問題 No.922 東北きりきざむたん
ユーザー kcvlexkcvlex
提出日時 2019-11-09 02:51:40
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
WA  
実行時間 -
コード長 5,646 bytes
コンパイル時間 1,767 ms
コンパイル使用メモリ 185,060 KB
実行使用メモリ 42,072 KB
最終ジャッジ日時 2023-10-13 06:38:34
合計ジャッジ時間 5,805 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,352 KB
testcase_01 AC 1 ms
4,352 KB
testcase_02 AC 1 ms
4,348 KB
testcase_03 AC 1 ms
4,348 KB
testcase_04 AC 2 ms
4,348 KB
testcase_05 WA -
testcase_06 WA -
testcase_07 AC 1 ms
4,352 KB
testcase_08 WA -
testcase_09 WA -
testcase_10 WA -
testcase_11 WA -
testcase_12 WA -
testcase_13 WA -
testcase_14 WA -
testcase_15 AC 34 ms
25,012 KB
testcase_16 WA -
testcase_17 WA -
testcase_18 WA -
testcase_19 WA -
testcase_20 WA -
testcase_21 AC 166 ms
33,032 KB
testcase_22 AC 165 ms
33,136 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 AC 141 ms
34,272 KB
testcase_26 WA -
testcase_27 AC 131 ms
33,900 KB
testcase_28 AC 60 ms
29,684 KB
testcase_29 AC 156 ms
42,072 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

// #define DEBUGGING
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define ALL(V) (V).begin(), (V).end()
#define ALLR(V) (V).rbegin(), (V).rend()
template <typename T> using V = std::vector<T>;
template <typename T> using VV = V<V<T>>;
using ll = std::int64_t;
using ull = std::uint64_t;
using PLL = std::pair<ll, ll>;
using TLL = std::tuple<ll, ll, ll>;
template <typename T> const T& var_min(const T &t) { return t; }
template <typename T> const T& var_max(const T &t) { return t; }
template <typename T, typename... Tail> const T& var_min(const T &t, const Tail&... tail) { return std::min(t, var_min(tail...)); }
template <typename T, typename... Tail> const T& var_max(const T &t, const Tail&... tail) { return std::max(t, var_max(tail...)); }
template <typename T, typename... Tail> void chmin(T &t, const Tail&... tail) { t = var_min(t, tail...); }
template <typename T, typename... Tail> void chmax(T &t, const Tail&... tail) { t = var_max(t, tail...); }
template <typename T> const T& clamp(const T &t, const T &low, const T &high) { return std::max(low, std::min(high, t)); }
template <typename T> void chclamp(T &t, const T &low, const T &high) { return t = clamp(t, low, high); }
namespace init__ { struct InitIO { InitIO() { std::cin.tie(nullptr); std::ios_base::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(30); } } init_io; }
#define mv_rec make_v(init, tail...)
template <typename T> T make_v(T init) { return init; }
template <typename T, typename... Tail> auto make_v(T init, size_t s, Tail... tail) { return V<decltype(mv_rec)>(s, mv_rec); }
#undef mv_rec
#ifdef DEBUGGING
#include "../../debug/debug.cpp"
#else
#define DEBUG(...) 0
#define DEBUG_SEPARATOR_LINE 0
#endif

ll N;
VV<ll> edges;
V<ll> cnt_from;
V<ll> prop_val;

PLL dfs1(ll cur, ll pre, ll prop, ll add_v) {
    ll add_sum = 0;
    add_v += cnt_from[cur];
    for(ll nxt : edges[cur]) if(nxt != pre) {
        ll a, b;
        tie(a, b) = dfs1(nxt, cur, prop + add_v, add_v);
        prop_val[cur] += a + b;
        add_sum += b;
    }
    ll fst = prop_val[cur];
    ll snd = add_sum + cnt_from[cur];
    prop_val[cur] += prop;
    return PLL(fst, snd);
}

ll dfs2(ll cur, ll pre, ll prop, ll add_v) {
    prop += add_v;
    ll ret = prop_val[cur] + prop;
    for(ll nxt : edges[cur]) if(nxt != pre) chmin(ret, dfs2(nxt, cur, prop, add_v));
    return ret;
}

ll calc_from_root(ll root) {
    V<PLL> ret_lis(edges[root].size());
    ll add_sum = 0;
    for(ll i = 0; i < edges[root].size(); i++) {
        ll a, b;
        tie(a, b) = dfs1(edges[root][i], root, cnt_from[root], cnt_from[root]);
        ret_lis[i] = PLL(a + b, b);
        prop_val[root] += a + b;
        add_sum += b;
    }
    ll ret = prop_val[root];
    for(ll i = 0; i < edges[root].size(); i++) {
        ll prop = prop_val[root] - ret_lis[i].first;
        ll add_v = add_sum - ret_lis[i].second;
        chmin(ret, dfs2(edges[root][i], root, prop, add_v));
    }
    return ret;
}

struct UnionFind {
    V<ll> parents, rank;

    UnionFind(ll N) : parents(N), rank(N, 1) {
        iota(ALL(parents), 0ll);
    }

    ll find(ll x) { return parents[x] == x ? x : parents[x] = find(parents[x]); }

    void unit(ll x, ll y) {
        ll px = find(x);
        ll py = find(y);
        if(px == py) return;
        if(rank[px] < rank[py]) swap(px, py);
        rank[px] += rank[px] == rank[py];
        parents[py] = px;
    }

    bool is_same(ll x, ll y) { return find(x) == find(y); }
};

struct LCA {
    V<ll> depth;
    VV<ll> dp;

    LCA(const VV<ll> &edges, const V<ll> &roots) 
        : depth(edges.size()), dp(make_v<ll>(0, edges.size(), 20)) {
        for(ll root : roots) dfs(root, -1, edges);
        for(ll k = 1; k < 20; k++) for(ll i = 0; i < edges.size(); i++) {
            ll p = dp[i][k - 1];
            if(p == -1) continue;
            dp[i][k] = dp[p][k - 1];
        }
    }

    void dfs(ll cur, ll pre, const VV<ll> &edges, ll d = 0) {
        dp[cur][0] = pre;
        depth[cur] = d;
        for(ll nxt : edges[cur]) if(nxt != pre) dfs(nxt, cur, edges, d + 1);
    }

    ll get_par(ll x, ll dist) {
        ll cur = x;
        for(ll k = 0; k < 20 && cur != -1; k++) if((dist >> k) & 1) cur = dp[cur][k];
        return cur;
    }

    ll get_lca(ll x, ll y) {
        if(depth[y] < depth[x]) swap(x, y);
        if(get_par(y, depth[y] - depth[x]) == x) return x;
        ll ok = 0, ng = max(depth[x], depth[y]);
        while(ng - ok > 1) {
            ll mid = (ok + ng) / 2;
            (get_par(x, mid) == get_par(y, mid) ? ok : ng) = mid;
        }
        return get_par(x, depth[x] - ok);
    }

    ll get_dist(ll x, ll y) {
        ll lca = get_lca(x, y);
        return (depth[x] - depth[lca]) +
               (depth[y] - depth[lca]);
    }
};

int main() {
    ll N, M, Q;
    cin >> N >> M >> Q;
    edges.resize(N);
    cnt_from.resize(N);
    prop_val.resize(N);
    UnionFind uf(N);
    while(M--) {
        ll u, v;
        cin >> u >> v;
        u--; v--;
        edges[u].push_back(v);
        edges[v].push_back(u);
        uf.unit(u, v);
    }

    V<ll> plis(N);
    for(ll i = 0; i < N; i++) plis[i] = uf.find(i);
    sort(ALL(plis));
    auto ite = unique(ALL(plis));
    plis.erase(ite, plis.end());

    LCA lca(edges, plis);
    ll ans = 0;
    while(Q--) {
        ll a, b;
        cin >> a >> b;
        a--; b--;
        if(uf.is_same(a, b)) {
            ans += lca.get_dist(a, b);
        } else {
            cnt_from[a]++;
            cnt_from[b]++;
        }
    }

    DEBUG(cnt_from);

    for(ll root : plis) ans += calc_from_root(root);
    cout << ans << endl;
    return 0;
}
0