結果

問題 No.922 東北きりきざむたん
コンテスト
ユーザー uzzy
提出日時 2019-11-09 00:52:03
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 86 ms / 2,000 ms
コード長 3,430 bytes
コンパイル時間 2,809 ms
コンパイル使用メモリ 195,028 KB
実行使用メモリ 27,008 KB
最終ジャッジ日時 2024-09-15 03:32:02
合計ジャッジ時間 5,245 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize ("O3")
#pragma GCC target ("avx")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i, n) for(int i = 0; i < (n); i++)
#define rep1(i, n) for(int i = 1; i <= (n); i++)
#define co(x) cout << (x) << "\n"
#define cosp(x) cout << (x) << " "
#define ce(x) cerr << (x) << "\n"
#define cesp(x) cerr << (x) << " "
#define pb push_back
#define mp make_pair
#define chmin(x, y) x = min(x, y)
#define chmax(x, y) x = max(x, y)
#define Would
#define you
#define please

int P[100001];
int Find(int A) {
	if (P[A] < 0) return A;
	return P[A] = Find(P[A]);
}

bool Unite(int A, int B) {
	int a = Find(A);
	int b = Find(B);
	if (a == b) return false;
	if (P[a] > P[b]) swap(a, b);
	P[a] += P[b];
	P[b] = a;
	return true;
}

int O[100001][17];
int D[100001];
int to[200002], ne[200002], he[100001], num[200002];

int oya(int A, int B) {
	if (B == 0) return A;
	int kazu = 0;
	int kari = B;
	while (kari > 1) {
		kazu++;
		kari /= 2;
	}
	return oya(O[A][kazu], B - (1 << kazu));
}

void dfs2(int A, int prev, int d) {
	D[A] = d;
	O[A][0] = prev;
	int mae = prev;
	rep(i, 16) {
		O[A][i + 1] = O[mae][i];
		mae = O[A][i + 1];
	}
	for (auto p = he[A]; p; p = ne[p]) {
		int To = to[p];
		if (To != prev) dfs2(To, A, d + 1);
	}
}

int N, M, Q;
int q[100001];
int dame[100001];
int K[100001];
ll S1[200002];
int S2[200002];

pair<ll, int> dfs(int v, int prev) {
	auto s1 = S1 + K[v - 1];
	auto s2 = S2 + K[v - 1];
	int sm = K[v] - K[v - 1];
	if (sm == 0) return mp(0, 0);
	if (!dame[v]) {
		dame[v] = prev;
		ll ret1 = 0;
		int ret2 = 0;
		int k = 0;
		for (int i = he[v]; i; i = ne[i]) {
			if (i != prev) {
				auto tmp = dfs(to[i], i ^ 1);
				ret1 += tmp.first;
				ret2 += tmp.second;
			}
			s1[k] = ret1;
			s2[k++] = ret2;
		}
	}

	if (dame[v] == prev) return mp(s1[sm - 1] + s2[sm - 1], s2[sm - 1] + q[v]);

	if (dame[v] != -1) {
		auto tmp = dfs(to[dame[v]], dame[v] ^ 1);
		int k = sm - num[dame[v]];
		for (int i = k - 1; i < sm; i++) {
			s1[i] += tmp.first;
			s2[i] += tmp.second;
		}
		dame[v] = -1;
	}
	if (prev == -1) return mp(s1[sm - 1] + s2[sm - 1], s2[sm - 1] + q[v]);
	int k = sm - num[prev];
	ll ret1 = s1[sm - 1] - s1[k - 1];
	int ret2 = s2[sm - 1] - s2[k - 1];
	if (k >= 2) {
		ret1 += s1[k - 2];
		ret2 += s2[k - 2];
	}
	return mp(ret1 + ret2, ret2 + q[v]);
}

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


	cin >> N >> M >> Q;

	rep1(i, N) P[i] = -1;
	int k = 2;
	rep(i, M) {
		int u, v;
		cin >> u >> v;
		num[k] = K[u]++;
		to[k] = v;
		ne[k] = he[u];
		he[u] = k++;
		num[k] = K[v]++;
		to[k] = u;
		ne[k] = he[v];
		he[v] = k++;

		Unite(u, v);
	}
	rep1(i, N) K[i] += K[i - 1];

	rep1(i, N) {
		if (Find(i) == i) {
			dfs2(i, 0, 0);
		}
	}

	ll kotae = 0;
	rep(i, Q) {
		int u, v;
		cin >> u >> v;
		if (Find(u) == Find(v)) {
			if (D[u] > D[v]) swap(u, v);
			int sa = D[v] - D[u];

			int u2 = u;
			int v2 = oya(v, sa);
			int lca = u;
			if (u2 != v2) {
				for (int k = 16; k >= 0; k--) {
					if (O[u2][k] != O[v2][k]) {
						u2 = O[u2][k];
						v2 = O[v2][k];
					}
				}
				lca = O[u2][0];
			}
			int dist = D[u] + D[v] - D[lca] * 2;
			kotae += dist;
		}
		else {
			q[u]++;
			q[v]++;
		}
	}

	ll saishou[100001];
	rep1(i, N) saishou[i] = 1e18;
	rep1(i, N) {
		int p = Find(i);
		saishou[p] = min(saishou[p], dfs(i, -1).first);
	}

	rep1(i, N) {
		if (Find(i) == i) {
			kotae += saishou[i];
		}
	}
	co(kotae);


	Would you please return 0;
}
0