結果

問題 No.922 東北きりきざむたん
ユーザー mugen_1337mugen_1337
提出日時 2020-08-30 01:53:49
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 622 ms / 2,000 ms
コード長 7,327 bytes
コンパイル時間 3,309 ms
コンパイル使用メモリ 239,612 KB
実行使用メモリ 66,800 KB
最終ジャッジ日時 2024-11-14 17:49:52
合計ジャッジ時間 9,655 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,820 KB
testcase_02 AC 2 ms
6,816 KB
testcase_03 AC 2 ms
6,816 KB
testcase_04 AC 3 ms
6,816 KB
testcase_05 AC 2 ms
6,816 KB
testcase_06 AC 3 ms
6,820 KB
testcase_07 AC 3 ms
6,820 KB
testcase_08 AC 3 ms
6,820 KB
testcase_09 AC 67 ms
10,368 KB
testcase_10 AC 37 ms
6,816 KB
testcase_11 AC 59 ms
8,960 KB
testcase_12 AC 50 ms
11,776 KB
testcase_13 AC 19 ms
6,820 KB
testcase_14 AC 104 ms
14,444 KB
testcase_15 AC 45 ms
12,672 KB
testcase_16 AC 204 ms
22,896 KB
testcase_17 AC 220 ms
24,304 KB
testcase_18 AC 209 ms
21,232 KB
testcase_19 AC 214 ms
23,416 KB
testcase_20 AC 209 ms
23,540 KB
testcase_21 AC 173 ms
16,632 KB
testcase_22 AC 175 ms
16,244 KB
testcase_23 AC 563 ms
42,340 KB
testcase_24 AC 622 ms
43,800 KB
testcase_25 AC 538 ms
45,976 KB
testcase_26 AC 530 ms
45,976 KB
testcase_27 AC 506 ms
45,932 KB
testcase_28 AC 69 ms
14,508 KB
testcase_29 AC 453 ms
66,800 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define ALL(x) x.begin(),x.end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define debug(v) cout<<#v<<":";for(auto x:v){cout<<x<<' ';}cout<<endl;
#define mod 1000000007
using ll=long long;
const int INF=1000000000;
const ll LINF=1001002003004005006ll;
int dx[]={1,0,-1,0},dy[]={0,1,0,-1};
// ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
template<class T>bool chmax(T &a,const T &b){if(a<b){a=b;return true;}return false;}
template<class T>bool chmin(T &a,const T &b){if(b<a){a=b;return true;}return false;}

struct IOSetup{
    IOSetup(){
        cin.tie(0);
        ios::sync_with_stdio(0);
        cout<<fixed<<setprecision(12);
    }
} iosetup;
 
template<typename T1,typename T2>
ostream &operator<<(ostream &os,const pair<T1,T2>&p){
    os<<p.first<<" "<<p.second;
    return os;
}
 
template<typename T>
ostream &operator<<(ostream &os,const vector<T>&v){
    for(int i=0;i<(int)v.size();i++) os<<v[i]<<(i+1==(int)v.size()?"":" ");
    return os;
}

template<typename T1,typename T2>
istream &operator>>(istream &is,pair<T1,T2>&p){
    is>>p.first>>p.second;
    return is;
}

template<typename T>
istream &operator>>(istream &is,vector<T>&v){
    for(T &x:v)is>>x;
    return is;
}

template<typename T>
struct rerooting{
    using F=function<T(T,int)>;//集合，頂点番号
    using M=function<T(T,T)>;
 
    int V;
    // dp_v = g(merge(f(dp_c1,c1),...,f(dp_ck,ck)),v)
    F f;    // TxN->T  マージする形に成形
    M merge;// TxT->T，子を集約する関数，モノイド
    T gen;
    F g;    // TxN->T  最後にdpの値を補正
    vector<vector<int>> G;
    vector<vector<T>> dp;
    vector<T> ans;
    
    //gen: mergeの元
    rerooting(int V,F f,M merge,T gen,F g=[](T a,int b){return a;})
        :V(V),f(f),merge(merge),gen(gen),g(g),G(V),dp(V),ans(V,gen){}
    
    //bidirectional
    void add_edge(int a,int b){
        G[a].push_back(b);
        G[b].push_back(a);
    }
    T dfs1(int pre,int now){
        T ret=gen;
        for(int i=0;i<(int)G[now].size();i++)if(G[now][i]!=pre){
            dp[now][i]=dfs1(now,G[now][i]);
            ret=merge(ret,f(dp[now][i],G[now][i]));
        }
        return g(ret,now);
    }
    void dfs2(int pre,int now,T frompar){
        for(int i=0;i<(int)G[now].size();i++){
            if(G[now][i]==pre){
                dp[now][i]=frompar;
                break;
            }
        }
        vector<T> lsum(G[now].size()+1),rsum(G[now].size()+1);//親も混ぜて累積
        lsum[0]=gen;rsum[G[now].size()]=gen;
        for(int i=0;i<(int)G[now].size();i++) lsum[i+1]=merge(lsum[i],f(dp[now][i],G[now][i]));
        for(int i=(int)G[now].size();i>0;i--) rsum[i-1]=merge(rsum[i],f(dp[now][i-1],G[now][i-1]));
        for(int i=0;i<(int)G[now].size();i++)if(G[now][i]!=pre){
            T fromme=merge(lsum[i],rsum[i+1]);
            dfs2(now,G[now][i],g(fromme,now));
        }
    }
    void build(int root=0){
        for(int i=0;i<V;i++) dp[i].resize(G[i].size());
        dfs1(-1,root);
        dfs2(-1,root,gen);
        for(int i=0;i<V;i++){
            for(int j=0;j<(int)G[i].size();j++) ans[i]=merge(ans[i],f(dp[i][j],G[i][j]));
            ans[i]=g(ans[i],i);
        }
    }
};

struct UnionFind{
    vector<int> par,siz;
    int con;
    UnionFind(int n){
        par.resize(n);
        iota(begin(par),end(par),0);
        siz.assign(n,1);
    }
    int root(int x){
        return (par[x]==x?x:(par[x]=root(par[x])));
    }
    bool sameroot(int x,int y){
        return root(x)==root(y);
    }
    bool unite(int x,int y){
        x=root(x);y=root(y);
        if(x==y) return false;
        if(siz[x]<siz[y])swap(x,y);
        siz[x]+=siz[y];
        par[y]=x;
        con--;
        return true;
    }
    int size(int x){
        return siz[root(x)];
    }
};

struct DoublingLowestCommonAncestor{
    const vector<vector<int>> &g;
    vector<int> dep;
    int LOG;
    //table[i][j]は点jの2^i個上の親情報
    vector<vector<int>> table;
 
    DoublingLowestCommonAncestor(const vector<vector<int>> &g):g(g),dep(g.size()),LOG(32-__builtin_clz(g.size())){
        table.assign(LOG,vector<int>(g.size(),-1));
    }
 
    void dfs(int idx,int par,int d){
        //1個上の親の記録
        table[0][idx]=par;
        dep[idx]=d;
        for(auto &to:g[idx]){
            if(to!=par) dfs(to,idx,d+1);
        }
    }
 
    //根としたい点をroot
    void build(int root){
        dfs(root,-1,0);
        for(int k=0;k+1<LOG;k++){
            for(int i=0;i<(int)table[k].size();i++){
                if(table[k][i]==-1) table[k+1][i]=-1;
                else table[k+1][i]=table[k][table[k][i]];
            }
        }
    }
 
    //u,vのlcaを求める
    int query(int u,int v){
        //dep[u]>dep[v]として進める
        if(dep[u]>dep[v]) swap(u,v);
        //深さをそろえる
        for(int i=LOG-1;i>=0;i--){
            if(((dep[v]-dep[u])>>i)&1) v=table[i][v];
        }
        if(u==v) return u;
        for(int i=LOG-1;i>=0;i--){
            if(table[i][u]!=table[i][v]){
                u=table[i][u];
                v=table[i][v];
            }
        }
        return table[0][u];
    }
    
    //呼び出すたびO(logn)
    int dis(int u,int v){
        int p=query(u,v);
        return dep[u]+dep[v]-2*dep[p];
    }
 
    //いるか？これ
    int operator[](const int &k) const{
        return dep[k];
    }
 
    //頂点xのk個上の親を求める。無ければ-1，未verify
    int parent(int x,int k){
        int ret=x;
        for(int i=LOG-1;i>=0 and ret>=0;i--){
            if((k>>i)&1) ret=table[i][ret];
        }
        return ret;
    }
};


signed main(){
    int n,m,q;cin>>n>>m>>q;
    UnionFind uf(n);

    using P=pair<int,int>;
    vector<P> es;

    rep(i,m){
        int u,v;cin>>u>>v;u--,v--;
        es.push_back(P(u,v));
        uf.unite(u,v);
    }    

    vector<vector<P>> ce(n);
    vector<vector<int>> cv(n);
    for(auto [u,v]:es){
        ce[uf.root(u)].push_back(P(u,v));
    }
    rep(i,n)cv[uf.root(i)].push_back(i);


    vector<vector<P>> qe(n);
    vector<int> cnt(n,0);
    rep(i,q){
        int u,v;cin>>u>>v;u--,v--;
        if(uf.sameroot(u,v))qe[uf.root(u)].push_back(P(u,v));
        else cnt[u]++,cnt[v]++;
    }

    ll res=0;
    rep(i,n){
        if(cv[i].empty())continue;

        map<int,int> id;
        int sz=0;
        for(auto x:cv[i])id[x]=sz++;
        vector<vector<int>> g(sz);
        vector<int> a(sz);

        auto f=[&](P fue,int v){return make_pair(fue.first+fue.second,fue.second);};
        auto merge=[&](P lhs,P rhs){return make_pair(lhs.first+rhs.first,lhs.second+rhs.second);};
        auto gf=[&](P fue,int v){return make_pair(fue.first,fue.second+a[v]);};

        rerooting<P> re(sz,f,merge,make_pair(0,0),gf);

        for(auto [u,v]:ce[i]){
            g[id[u]].push_back(id[v]);
            g[id[v]].push_back(id[u]);
            re.add_edge(id[u],id[v]);
        }

        for(auto x:cv[i])a[id[x]]=cnt[x];

        re.build();

        DoublingLowestCommonAncestor lca(g);
        lca.build(0);
        for(auto [u,v]:qe[i]){
            res+=lca.dis(id[u],id[v]);
        }


        int mugen=INF;
        
        rep(j,sz){
            chmin(mugen,re.ans[j].first);
        }

        res+=mugen;
    }
    cout<<res<<endl;
    return 0;
}
0