結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー leaf_1415
提出日時 2019-11-08 22:08:05
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
WA  
実行時間 -
コード長 3,090 bytes
コンパイル時間 1,596 ms
コンパイル使用メモリ 66,428 KB
実行使用メモリ 28,856 KB
最終ジャッジ日時 2024-09-15 01:31:06
合計ジャッジ時間 5,432 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9 WA * 17
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#define llint long long
#define inf 1e18

using namespace std;

struct UnionFind{
	int size;
	vector<int> parent;

	UnionFind(){}
	UnionFind(int size){
		this->size = size;
		parent.resize(size+1);
		init();
	}
	void init(){
		for(int i = 0; i <= size; i++) parent[i] = i;
	}
	int root(int i){
		if(parent[i] == i) return i;
		return parent[i] = root(parent[i]);
	}
	bool same(int i, int j){
		return root(i) == root(j);
	}
	void unite(int i, int j){
		int root_i = root(i), root_j = root(j);
		if(root_i == root_j) return;
		parent[root_i] = root_j;
	}
};

llint n, m, Q;
vector<llint> G[100005];
vector<llint> qvec[100005];
UnionFind uf(100005);
bool used[100005];
llint w[100005];

vector<llint> vec;
int Prev[100005][17];
int depth[100005];
int size[100005];

int getLCA(int u, int v){
	int x = u, y = v;
	if(depth[y] > depth[x]) swap(x, y);

	for(int i = 16; i >= 0; i--){
		if(depth[x] - (1<<i) >= depth[y]) x = Prev[x][i];
	}
	if(x == y) return x;
	for(int i = 16; i >= 0; i--){
		if(Prev[x][i] != Prev[y][i]){
			x = Prev[x][i];
			y = Prev[y][i];
		}
	}
	x = Prev[x][0];
	return x;
}

int dfs(int v, int p, int d)
{
  used[v] = true;
  Prev[v][0] = p;
  depth[v] = d;
  vec.push_back(v);
  int ret = 1;
  for(int i = 0; i < G[v].size(); i++){
    if(G[v][i] == p) continue;
    ret += dfs(G[v][i], v, d+1);
  }
  return ret;
}

int sizedfs(int v, int pre)
{
	int ret = w[v];
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == pre) continue;
		ret += sizedfs(G[v][i], v);
	}
	return size[v] = ret;
}

int centdfs(int v, int pre, int sz)
{
	for(int i = 0; i < G[v].size(); i++){
		if(G[v][i] == pre) continue;
		if(size[G[v][i]] > sz/2) return centdfs(G[v][i], v, sz);
	}
	return v;
}

llint calc(llint r)
{
  vec.clear();
  dfs(r, 0, 0);
  for(int j = 0; j < 17; j++){
    for(int i = 0; i < vec.size(); i++){
      int v = vec[i];
      Prev[v][j] = Prev[Prev[v][j-1]][j-1];
    }
  }
  llint ret = 0;
  for(int i = 0; i < vec.size(); i++){
    int v = vec[i];
    for(int j = 0; j < qvec[v].size(); j++){
      int u = qvec[v][j];
      if(uf.same(v, u)) ret += depth[v] + depth[u] - 2*depth[getLCA(u, v)];
      else w[v]++;
    }
  }

  sizedfs(r, -1);
  llint x = centdfs(r, -1, size[r]);
  vec.clear();
  dfs(x, 0, 0);

  //cout << x << " " << ret << endl;

  for(int i = 0; i < vec.size(); i++){
    int v = vec[i];
    ret += depth[v] * w[v];
  }
  //cout << ret << endl;
  return ret;
}

int main(void)
{
  ios::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> Q;
  llint u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
    uf.unite(u, v);
  }
  llint a, b;
  for(int i = 1; i <= Q; i++){
    cin >> a >> b;
    if(a > b) swap(a, b);
    qvec[a].push_back(b);
    if(!uf.same(a, b)) qvec[b].push_back(a);
  }

  llint ans = 0;
  for(int i = 1; i <= n; i++){
    if(!used[i]) ans += calc(i);
  }
  cout << ans << endl;

  //for(int i = 1; i <= n; i++) cout << w[i] << " "; cout << endl;
  //for(int i = 1; i <= n; i++) cout << depth[i] << " "; cout << endl;

  return 0;
}
0