結果

問題 No.922 東北きりきざむたん
ユーザー leaf_1415leaf_1415
提出日時 2019-11-08 22:14:00
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 159 ms / 2,000 ms
コード長 3,094 bytes
コンパイル時間 1,781 ms
コンパイル使用メモリ 66,364 KB
実行使用メモリ 29,180 KB
最終ジャッジ日時 2023-10-13 03:56:33
合計ジャッジ時間 5,352 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge11
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,132 KB
testcase_01 AC 4 ms
9,004 KB
testcase_02 AC 5 ms
9,000 KB
testcase_03 AC 4 ms
8,960 KB
testcase_04 AC 4 ms
9,028 KB
testcase_05 AC 4 ms
9,004 KB
testcase_06 AC 5 ms
9,184 KB
testcase_07 AC 5 ms
9,280 KB
testcase_08 AC 5 ms
9,264 KB
testcase_09 AC 42 ms
17,324 KB
testcase_10 AC 34 ms
14,364 KB
testcase_11 AC 42 ms
16,984 KB
testcase_12 AC 21 ms
17,532 KB
testcase_13 AC 16 ms
12,904 KB
testcase_14 AC 72 ms
21,644 KB
testcase_15 AC 15 ms
17,208 KB
testcase_16 AC 128 ms
24,512 KB
testcase_17 AC 135 ms
24,280 KB
testcase_18 AC 132 ms
24,300 KB
testcase_19 AC 134 ms
24,436 KB
testcase_20 AC 133 ms
24,528 KB
testcase_21 AC 159 ms
24,444 KB
testcase_22 AC 159 ms
24,328 KB
testcase_23 AC 158 ms
24,060 KB
testcase_24 AC 147 ms
23,920 KB
testcase_25 AC 126 ms
24,320 KB
testcase_26 AC 125 ms
24,348 KB
testcase_27 AC 129 ms
24,324 KB
testcase_28 AC 59 ms
20,680 KB
testcase_29 AC 124 ms
29,180 KB
権限があれば一括ダウンロードができます

ソースコード

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];
llint depth[100005];
llint 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 = 1; 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