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

• 問題: No.922 東北きりきざむたん
• ユーザー: RTnF
• 提出日時: 2019-11-08 23:32:44
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 169 ms / 2,000 ms
• コード長: 7,780 bytes
• コンパイル時間: 3,431 ms
• コンパイル使用メモリ: 245,560 KB
• 実行使用メモリ: 59,884 KB
• 最終ジャッジ日時: 2024-09-15 02:41:36
• 合計ジャッジ時間: 7,354 ms
• ジャッジサーバーID （参考情報）: judge2 / judge6

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	2 ms; 6,816 KB
testcase_01	AC	2 ms; 6,816 KB
testcase_02	AC	2 ms; 6,940 KB
testcase_03	AC	2 ms; 6,940 KB
testcase_04	AC	2 ms; 6,944 KB
testcase_05	AC	2 ms; 6,940 KB
testcase_06	AC	3 ms; 6,944 KB
testcase_07	AC	3 ms; 6,940 KB
testcase_08	AC	3 ms; 6,940 KB
testcase_09	AC	89 ms; 25,188 KB
testcase_10	AC	32 ms; 8,324 KB
testcase_11	AC	71 ms; 18,752 KB
testcase_12	AC	94 ms; 45,700 KB
testcase_13	AC	29 ms; 12,696 KB
testcase_14	AC	158 ms; 42,852 KB
testcase_15	AC	94 ms; 51,140 KB
testcase_16	AC	142 ms; 27,364 KB
testcase_17	AC	141 ms; 27,568 KB
testcase_18	AC	150 ms; 27,668 KB
testcase_19	AC	153 ms; 27,484 KB
testcase_20	AC	147 ms; 27,380 KB
testcase_21	AC	131 ms; 24,616 KB
testcase_22	AC	137 ms; 24,616 KB
testcase_23	AC	159 ms; 27,048 KB
testcase_24	AC	163 ms; 27,176 KB
testcase_25	AC	132 ms; 26,792 KB
testcase_26	AC	124 ms; 26,792 KB
testcase_27	AC	126 ms; 26,908 KB
testcase_28	AC	169 ms; 59,884 KB
testcase_29	AC	121 ms; 29,224 KB

ソースコード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using vi = vector<int>;
using vvi = vector<vi>;
using vvvi = vector<vvi>;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pll = pair<ll, ll>;
using vp = vector<pll>;
#define rep(i, n) for(ll i = 0; i < (n); i++)
#define repb(i, n) for(ll i = (n)-1; i >= 0; i--)
#define repr(i, a, b) for(ll i = (a); i < (b); i++)
#define reprb(i, a, b) for(ll i = (b)-1; i >= (a); i--)
#define ALL(a) (a).begin(), (a).end()
#define SZ(x) ((ll)(x).size())
const ll MOD = 1000000007;
const ll INF = 100000000000000000LL;
const ld EPS = 1e-12L;
const ld PI = 3.1415926535897932385L;
inline ll GCD(ll a, ll b){ return b?GCD(b, a % b):a; }
inline ll LCM(ll a, ll b){ return a/GCD(a, b)*b; }
inline ll powint(ull x, ll y){ ll r=1; while(y){ if(y&1) r*=x; x*=x; y>>=1; } return r; }
inline ll powmod(ll x, ll y, ll m = MOD){ ll r=1; while(y){ if(y&1) r*=x; x*=x; r%=m; x%=m; y>>=1; } return r; }
template<class S, class T>inline bool chmax(S &a, const T &b){ if(a<b) { a=b; return 1; } return 0; }
template<class S, class T>inline bool chmin(S &a, const T &b){ if(b<a) { a=b; return 1; } return 0; }
#ifdef OJ_LOCAL
#include "dump.hpp"
#else
#define dump(...) ((void)0)
#endif

template<typename T> struct Edge {
    int from, to;
    T cost;
    Edge(int from, int to, T cost): from(from), to(to), cost(cost) {}
    Edge(int from, int to): from(from), to(to), cost(1) {}
    bool operator<(Edge<T> &r) {
        return cost < r.cost;
    }
};
template<typename T>
ostream &operator<<(ostream &os, Edge<T> edge) {
    os << edge.from << " -> " << edge.to << " (" << edge.cost << ")";
    return os;
}

// グラフテンプレート(隣接リスト)
template<typename E = Edge<ll>> struct GraphL {
    // 頂点数、辺数
    int n, m;
    // 隣接リスト
    vector<vector<E>> adj;
    GraphL(int n)
        : n(n), m(0), adj(n), sum(n, 0), dep(n, 0), cnt(n, 0), visited(n, false) {}
    
    template<typename... Args>
    void add_edge(int from, int to, Args... args) {
        adj[from].emplace_back(from, to, args...);
        m++;
    }
    
    vll sum;
    vll cnt;
    vector<bool> visited;
    ll dfs(ll s){
        ll ret = cnt[s];
        visited[s] = true;
        for(auto&& e: adj[s])if(!visited[e.to]){
            ret += dfs(e.to);
        }
        return sum[s] = ret;
    }
    ll dfs2(ll s){
        visited[s] = true;
        dump(s);
        for(auto&& e: adj[s])if(!visited[e.to]){
            if(sum[e.to] > sum[0]/2){
                return dfs2(e.to);
            }
        }
        return s;
    }
    vector<int> dep;
    void dfs3(ll s, ll d){
        visited[s] = true;
        dep[s] = d;
        for(auto&& e: adj[s])if(!visited[e.to]){
            dfs3(e.to, d+1);
        }
    }
    ll solve(){
        dfs(0);
        fill(ALL(visited), false);
        ll t = dfs2(0);
        fill(ALL(visited), false);
        dfs3(t, 0);
        ll ret = 0;
        rep(i, n){
            ret += cnt[i]*dep[i];
        }
        return ret;
    }
};
template<typename E = Edge<ll>>
ostream &operator<<(ostream &os, GraphL<E> graph) {
    os << "V = " << graph.n << ", E = " << graph.m << "\n";
    for(const auto& ev: graph.adj) {
        for(const auto& e: ev) {
            os << e << "\n";
        }
    }
    return os;
}

struct LCA {
    // m = [lg(n-1)]
    int m, n;
    vector<vector<int>> ancestor;
    vector<int> depth;
    template<typename E>
    LCA(const GraphL<E>& graph, int root = 0): n(graph.n) {
        assert(graph.n >= 1);
        m = 32 - __builtin_clz(graph.n - 1);
        ancestor.resize(m, vector<int>(n));
        depth.resize(n, -1);
        auto dfs = [&](auto& Self, int node, int parent, int d) {
            ancestor[0][node] = parent;
            depth[node] = d;
            if(graph.adj[node].size() == 0) return;
            for(const auto& e: graph.adj[node])
                if(depth[e.to] == -1)
                    Self(Self, e.to, node, d + 1);
        };
        dfs(dfs, root, -1, 0);
        for(int i = 1; i < m; i++) {
            for(int j = 0; j < n; j++) {
                if(ancestor[i - 1][j] == -1) {
                    ancestor[i][j] = -1;
                } else {
                    ancestor[i][j] = ancestor[i - 1][ancestor[i - 1][j]];
                }
            }
        }
    }
    int query(int node1, int node2) {
        if(depth[node1] > depth[node2]) swap(node1, node2);
        for(int i = m - 1; i >= 0; i--)
            if(((depth[node2] - depth[node1]) >> i) & 1)
                node2 = ancestor[i][node2];
        if(node1 == node2) return node1;
        for(int i = m - 1; i >= 0; i--) {
            if(ancestor[i][node1] != ancestor[i][node2]) {
                node1 = ancestor[i][node1];
                node2 = ancestor[i][node2];
            }
        }
        return ancestor[0][node1];
    }
    int distance(int node1, int node2) {
        return depth[node1] + depth[node2] - 2 * depth[query(node1, node2)];
    }
};

struct UnionFind {
    // 木の頂点数と高さは根の値のみ意味がある
    vector<int> par, sizes, rank;
    UnionFind(int n) : par(n), sizes(n, 1), rank(n, 0) {
        for(int i = 0; i < n; i++) par[i] = i;
    }
    int find(int x) {
        if(x == par[x]) return x;
        return par[x] = find(par[x]); // recursive, editing root
    }
    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if(x == y) return;
        if(rank[x] < rank[y]) swap(x, y);
        par[y] = x;
        sizes[x] += sizes[y];
        if(rank[x] == rank[y]) rank[x]++;
    }
    bool same(int x, int y) { return find(x) == find(y); }
    int size(int x) { return sizes[find(x)]; }
};

// {10, 3, 1, -5, 1} -> {3, 2, 1, 0, 1}
template<typename T>
vector<T> CoordinateCompression(vector<T> &x){
    int n = x.size();
    vector<T> y = x, ret(n);
    sort(y.begin(), y.end());
    y.erase(unique(y.begin(), y.end()), y.end());
    for(int i = 0; i < n; i++) {
        ret[i] = lower_bound(y.begin(), y.end(), x[i]) - y.begin();
    }
    return ret;
}

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    ll N, M, Q;
    cin >> N >> M >> Q;
    UnionFind uf(N);
    vll u(M), v(M);
    rep(i, M){
        cin >> u[i] >> v[i];
        u[i]--; v[i]--;
        uf.unite(u[i], v[i]);
    }
    vll group(N);
    rep(i, N){
        group[i] = uf.find(i);
    }
    group = CoordinateCompression(group);
    ll group_num = *max_element(ALL(group)) + 1;
    vll group_size(group_num);
    vvll group_v(group_num);
    vll group_find(N);
    rep(i, N){
        group_size[group[i]] = uf.size(i);
        group_v[group[i]].emplace_back(i);
    }
    rep(i, group_num){
        rep(j, SZ(group_v[i])){
            group_find[group_v[i][j]] = j;
        }
    }
    vector<GraphL<>> g;
    rep(i, group_num){
        g.emplace_back(group_size[i]);
    }
    rep(i, M){
        ll x = group[u[i]];
        g[x].add_edge(group_find[u[i]], group_find[v[i]]);
        g[x].add_edge(group_find[v[i]], group_find[u[i]]);
    }
    vector<LCA> lca;
    rep(i, group_num){
        lca.emplace_back(g[i]);
    }
    ll ans = 0;
    vll a(Q), b(Q);
    rep(i, Q){
        cin >> a[i] >> b[i];
        a[i]--; b[i]--;
        if(uf.same(a[i], b[i])){
            ans += lca[group[a[i]]].distance(group_find[a[i]], group_find[b[i]]);
        }else{
            g[group[a[i]]].cnt[group_find[a[i]]]++;
            g[group[b[i]]].cnt[group_find[b[i]]]++;
        }
    }
    rep(i, group_num){
        ans += g[i].solve();
        dump(g[i].cnt);
        dump(g[i].dep);
        dump(g[i].sum);
    }
    cout << ans << endl;
    return 0;
}