結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー tanimani364
提出日時 2019-11-08 22:57:54
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 2,969 bytes
コンパイル時間 1,197 ms
コンパイル使用メモリ 102,612 KB
実行使用メモリ 814,592 KB
最終ジャッジ日時 2024-09-15 02:05:42
合計ジャッジ時間 5,529 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other WA * 5 MLE * 1 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<iostream>
#include<string>
#include<vector>
#include<algorithm>
#include<map>
#include<set>
#include<cstdio>
#include<cmath>
#include<numeric>
#include<queue>
#include<stack>
#include<cstring>
#include<limits>
#include<functional>
#include<unordered_set>
#include<iomanip>
#include<cassert>
#define rep(i,a) for(int i=(int)0;i<(int)a;++i)
#define pb push_back
#define eb emplace_back
using ll=long long;
constexpr ll mod = 1e9 + 7;
constexpr ll INF = 1LL << 50;
 
template<class T> inline bool chmin(T& a, T b) {
    if (a > b) {
        a = b;
        return true;
    }
    return false;
}
template<class T> inline bool chmax(T& a, T b) {
    if (a < b) {
        a = b;
        return true;
    }
    return false;
}
using namespace std;

//ワーシャルフロイド法、全点対最短路
//実装例
const int INFTY=(numeric_limits<int>::max())/2;
vector<vector<int>>d;//d[u][v]は辺uvのコスト、ただし存在しないときINFTY,d[i][i]=0

void warshall_floyd(int V){//Vは頂点数
	for(int k=0;k<V;++k){//経由する頂点
		for(int i=0;i<V;++i){//始点となる頂点
			for(int j=0;j<V;++j)//目的地の頂点
      d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		}
	}
}



 struct UF {
	vector<int>par;//親
	vector<int>Rank;//木の深さ
    vector<int>sz;//要素数

    UF(int n){init(n);}

	//初期化
	void init(int n) {
		par.resize(n); Rank.resize(n);sz.resize(n);
		for (int i = 0; i < n; i++) {
			par[i]= i;
			Rank[i] = 0;
            sz[i]=1;
		}
	}

	//木の根を求める
	int find(int x) {
		if (par[x] == x) {
			return x;
		}
		else {
			return par[x] = find(par[x]);
		}
	}

	//xとyの属する集合を併合
	bool unite(int x, int y) {
		x = find(x);
		y = find(y);
		if (x == y)return false;//すでに同じ集合に属している

		if (Rank[x] < Rank[y]) {//高さが小さい方を下に
			par[x] = y;
            sz[y]+=sz[x];
		}
		else {
			par[y] = x;
			if (Rank[x] == Rank[y])Rank[x]++;//同じだとrankが変わらないままになるので増やす（それ以外は大きい方のrankが採用される）
            sz[x]+=sz[y];
		}
		return true;
	}

	//xとyが同じ集合に属するかを判定
	bool same(int x, int y) {
		return find(x) == find(y);
	}

    int size(int k){//要素数を求める
        return sz[find(k)];
    }
};



void solve(){
    int n,m,q;
    cin>>n>>m>>q;
    d.resize(n,vector<int>(n,INFTY));
    UF tree(n);
    rep(i,m){
        int u,v;
        cin>>u>>v;
        u--;v--;
        tree.unite(u,v);
        d[u][v]=d[v][u]=1;
    }
    vector<int>a(q),b(q);
    rep(i,q){
        cin>>a[i]>>b[i];
        a[i]--;b[i]--;
        if(!tree.same(a[i],b[i])){
            d[a[i]][b[i]]=d[b[i]][a[i]]=0;
            tree.unite(a[i],b[i]);
        }
    }
    warshall_floyd(n);
    int sum=0;
    rep(i,q)sum+=d[a[i]][b[i]];
    cout<<sum<<endl;
}
 
signed main(){
	ios::sync_with_stdio(false);
    cin.tie(0);
	cout<<fixed<<setprecision(15);
	solve();
	return 0;
}
0