結果

問題 No.922 東北きりきざむたん
ユーザー algon_320algon_320
提出日時 2019-11-08 22:14:02
言語 C++14
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 183 ms / 2,000 ms
コード長 6,044 bytes
コンパイル時間 2,812 ms
コンパイル使用メモリ 186,796 KB
実行使用メモリ 43,656 KB
最終ジャッジ日時 2023-10-13 03:56:48
合計ジャッジ時間 6,360 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
4,372 KB
testcase_01 AC 2 ms
4,372 KB
testcase_02 AC 1 ms
4,368 KB
testcase_03 AC 1 ms
4,372 KB
testcase_04 AC 2 ms
4,372 KB
testcase_05 AC 2 ms
4,368 KB
testcase_06 AC 2 ms
4,368 KB
testcase_07 AC 2 ms
4,372 KB
testcase_08 AC 2 ms
4,368 KB
testcase_09 AC 37 ms
11,412 KB
testcase_10 AC 26 ms
5,896 KB
testcase_11 AC 32 ms
9,564 KB
testcase_12 AC 16 ms
12,352 KB
testcase_13 AC 9 ms
5,536 KB
testcase_14 AC 58 ms
16,404 KB
testcase_15 AC 12 ms
12,920 KB
testcase_16 AC 138 ms
18,636 KB
testcase_17 AC 140 ms
18,692 KB
testcase_18 AC 146 ms
18,640 KB
testcase_19 AC 139 ms
18,620 KB
testcase_20 AC 144 ms
18,480 KB
testcase_21 AC 141 ms
18,164 KB
testcase_22 AC 146 ms
17,960 KB
testcase_23 AC 180 ms
26,680 KB
testcase_24 AC 183 ms
27,964 KB
testcase_25 AC 143 ms
28,264 KB
testcase_26 AC 136 ms
28,360 KB
testcase_27 AC 140 ms
28,280 KB
testcase_28 AC 33 ms
14,960 KB
testcase_29 AC 130 ms
43,656 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define stoi stoll
using pii=pair<int,int>;
using vi = vector<int>;
using vvi = vector<vi>;
#define all(c) begin(c),end(c)
#define rall(c) rbegin(c),rend(c)
#define fore(x,c) for(auto &&x:c)
#define rep(i,a,n) for(int i=a,i##len=(int)(n);i<i##len;++i)
#define rrep(i, a, n) for(int i=(int)(n-1);i>=a;--i)
#define sz(c) ((int)c.size())
#define contains(c,x) (c.find(x)!=end(c))
#define inseg(l,x,r) ((l)<=(x)&&(x)<(r))
#define dump(...)
#define pb push_back
#define _ 0
const signed INF_=1001001001; const long long INF=1001001001001001001LL;
const int DX[9]={0,1,0,-1,1,1,-1,-1,0},DY[9]={-1,0,1,0,-1,1,1,-1,0};
template<class T> ostream& operator<<(ostream &os,const vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) os<<*i<<(i==end(v)-1?"":" ");return os;}
template<class T> istream& operator>>(istream &is,vector<T> &v) {
    for (auto i = begin(v); i != end(v); i++) is>>*i;return is;}
template<class T,class U> istream& operator>>(istream &is, pair<T,U> &p) {
    is>>p.first>>p.second;return is;}
template<class T, class U> bool chmax(T &a,const U &b){return a<b?a=b,1:0;}
template<class T, class U> bool chmin(T &a,const U &b){return a>b?a=b,1:0;}
template <class T> void psum(T& c) {partial_sum(begin(c), end(c), begin(c));}
template<class T> using heap=priority_queue<T,vector<T>,greater<T>>;
struct before_main_function {
    before_main_function() {
        cin.tie(nullptr); ios::sync_with_stdio(0);
        cout << setprecision(15) << fixed;
        // #define endl "\n"
    }
} before_main_function;
//------------------8<------------------------------------8<--------------------

struct union_find {
    vector<int> data;
    int comp;
    union_find(int size) : data(size, -1), comp(size) {}
    void unite(int x, int y) {
        x = root(x); y = root(y);
        if(x != y) {
            if(data[y] < data[x]) swap(x, y);
            data[x] += data[y];
            data[y] = x;
            comp--;
        }
    }
    bool same(int x, int y) {
        return root(x) == root(y);
    }
    int root(int x) {
        return data[x] < 0 ? x : (data[x] = root(data[x]));
    }
    int size(int x) {
        return -data[root(x)];
    }
    int components() { return comp; }
};

struct LCA {
    using Query = pii;

    const vvi &g;
    vi color;
    vi ancestor;
    vector<vector<pair<int, Query>>> query_set;
    union_find uf;
    vi res;
    vi dist;

    LCA(const vvi &g, vector<Query> &query) :
            g         (g),
            color     (sz(g)),
            ancestor  (sz(g)),
            query_set (sz(g)),
            uf        (sz(g)),
            res       (sz(query)),
            dist      (sz(g))
    {
        int qs = sz(query);
        rep(i, 0, qs) {
            query_set[query[i].first ].emplace_back(i, query[i]);
            query_set[query[i].second].emplace_back(i, query[i]);
        }
    }

    void visit(int v, int prev, int d) {
        ancestor[uf.root(v)] = v;
        for (auto &w : g[v]) {
            if (w == prev) {
                continue;
            }
            visit(w, v, d + 1);
            uf.unite(v, w);
            ancestor[uf.root(v)] = v;
        }
        dist[v] = d;
        color[v] = 1;
        for (auto &p : query_set[v]) {
            Query q = p.second;
            int w = (q.second == v ? q.first
                    : (q.first == v ? q.second : -1));
            if (w == -1 || !color[w]) {
                continue;
            }
            res[p.first] = ancestor[uf.root(w)];
        }
    }

    vi solve(int root) {
        visit(root, -1, 0);
        return res;
    }
};

signed main() {
    int N, M, Q;
    cin >> N >> M >> Q;
    vector<vector<int>> G(N);
    vector<int> num(N);
    rep(i, 0, M) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    vector<int> comp(N, -1);
    vector<int> roots;
    rep(i, 0, N) {
        if (comp[i] != -1) continue;
        static int comp_id = 0;
        roots.push_back(i);
        comp_id++;
        comp[i] = comp_id;
        auto dfs = [&](auto fun, int v) -> void {
            comp[v] = comp_id;
            for (int w : G[v]) {
                if (comp[w] != -1) continue;
                fun(fun, w);
            }
        };
        dfs(dfs, i);
    }

    int ans = 0;
    vector<pii> lca_query;

    rep(i, 0, Q) {
        int a, b;
        cin >> a >> b;
        a--, b--;
        if (comp[a] == comp[b]) {
            lca_query.push_back({a, b});
        } else {
            num[a]++;
            num[b]++;
        }
    }

    vector<pii> dp(N, pii(0, 0));
    for (int root : roots) {
        auto dfs1 = [&](auto fun, int v, int p) -> void {
            pii cnt_dist = {num[v], 0};
            for (int w : G[v]) {
                if (w == p) continue;
                fun(fun, w, v);
                cnt_dist.first += dp[w].first;
                cnt_dist.second += dp[w].second + dp[w].first;
            }
            dp[v] = cnt_dist;
        };
        dfs1(dfs1, root, -1);
        auto dfs2 = [&](auto fun, int v, int p, pii upper) -> int {
            int ret = INF;
            int tmp = dp[v].second + upper.second;
            for (int w : G[v]) {
                if (w == p) continue;
                int c = dp[v].first - dp[w].first + upper.first;
                int d = dp[v].second - (dp[w].second + dp[w].first) + c + upper.second;
                chmin(ret, fun(fun, w, v, {c, d}));
            }
            chmin(ret, tmp);
            return ret;
        };
        int mn = dfs2(dfs2, root, -1, {0, 0});
        ans += mn;
    }
    
    {
        LCA lca(G, lca_query);
        for (int r : roots) {
            lca.solve(r);
        }
        rep(i, 0, sz(lca_query)) {
            int a = lca_query[i].first;
            int b = lca_query[i].second;
            int l = lca.res[i];
            ans += lca.dist[a] + lca.dist[b] - 2 * lca.dist[l];
        }
    }

    cout << ans << endl;
    return (0^_^0);
}
0