結果

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

ソースコード

diff # 

#include "bits/stdc++.h"

using namespace std;
#ifdef _DEBUG
#define _GLIBCXX_DEBUG
#include "dump.hpp"
#else
#define dump(...)
#endif

#define int long long
#define ll long long
#define DBG 1
#define rep(i, a, b) for (int i = (a); i < (b); i++)
#define rrep(i, a, b) for (int i = (b)-1; i >= (a); i--)
#define loop(n) rep(loop, (0), (n))
#define all(c) begin(c), end(c)
const int INF = sizeof(int) == sizeof(long long) ? 0x3f3f3f3f3f3f3f3fLL : 0x3f3f3f3f;
const int MOD = (int)(1e9) + 7;
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
using pii = pair<int, int>;
// template<class T> ostream &operator<<(ostream &os,T &t){dump(t);return os;}
template <typename T, typename S>istream &operator>>(istream &is, pair<T, S> &p) { is >> p.first >> p.second; return is; }
//template <typename T, typename S>ostream &operator<<(ostream &os, pair<T, S> &p) {os << p.first << " " << p.second;return os;}

template <typename T> void printvv(const vector<vector<T>> &v) {
	cerr << endl;
	rep(i, 0, v.size()) rep(j, 0, v[i].size()) {
		if (typeid(v[i][j]).name() == typeid(INF).name() and v[i][j] == INF) {
			cerr << "INF";
		}
		else
			cerr << v[i][j];
		cerr << (j == v[i].size() - 1 ? '\n' : ' ');
	}
	cerr << endl;
}

#ifndef _DEBUG
#define printvv(...)
#endif
void YES(bool f) { cout << (f ? "YES" : "NO") << endl; }
void Yes(bool f) { cout << (f ? "Yes" : "No") << endl; }
template <class T, class U>bool chmin(T& a, U b) { if (a > b) { a = b; return true; }return false; }
template <class T, class U>bool chmax(T& a, U b) { if (a < b) { a = b; return true; }return false; }
using Weight = int;
using Flow = int;
struct Edge {
	int s, d; Weight w; Flow c; int id;
	Edge() {};
	Edge(int s, int d, Weight w = 1) : s(s), d(d), w(w), c(w) {};
};
bool operator<(const Edge &e1, const Edge &e2) { return e1.w < e2.w; }
bool operator>(const Edge &e1, const Edge &e2) { return e2 < e1; }
inline ostream &operator<<(ostream &os, const Edge &e) { return (os << '(' << e.s << ", " << e.d << ", " << e.w << ')'); }

using Edges = vector<Edge>;
using Graph = vector<Edges>;
using Array = vector<Weight>;
using Matrix = vector<Array>;

void addArc(Graph &g, int s, int d, Weight w = 1) {
	g[s].emplace_back(s, d, w);
}
void addEdge(Graph &g, int a, int b, Weight w = 1) {
	addArc(g, a, b, w);
	addArc(g, b, a, w);
}

struct UnionFind {
	vector<int> parent;
	int size;
	UnionFind(int n) :parent(n, -1), size(n) {}
	bool unite(int x, int y) {
		x = root(x); y = root(y);
		if (x == y)return false;
		if (size_of(x) < size_of(y))swap(x, y);
		parent[x] += parent[y]; parent[y] = x; size--;
		return true;
	}
	bool same(int x, int y) { return root(x) == root(y); }
	int root(int x) { return parent[x] < 0 ? x : parent[x] = root(parent[x]); }
	int size_of(int x) { return -parent[root(x)]; }
};
struct LCA { // rooted tree
	using Node = int;
	vector<vector<Node>> parent;
	Graph g;
	int root, V, log2_n;
	vector<Node> depth;
	vector<Weight>dist;
	int get_depth(int x) { return depth[x]; }

	void dfs(int v, int p, int _depth, Weight w) {
		dump(v, p, _depth, w);
		parent[0][v] = p;
		depth[v] = _depth;
		dist[v] = w;
		for (const auto &e : g[v]) {
			if (e.d == p)continue;
			dfs(e.d, v, _depth + 1, w + e.w);
		}
	}
	LCA(const Graph &G, int root)
		: root(root), V(G.size()), g(G), depth(V), log2_n(1 + (int)log2(V)), dist(V) {
		dump(root);
		parent.resize(log2_n, vector<Node>(V));
		dfs(root, -1, 0, 0);
		for (int k = 0; k + 1 < log2_n; k++) {
			for (int v = 0; v < V; v++) {
				auto p = parent[k][v];
				if (p < 0) {
					parent[k + 1][v] = -1;
				}
				else {
					parent[k + 1][v] = parent[k][p];
				}
			}
		}
	}
	Node query(int u, int v) {
		if (depth[u] > depth[v])
			swap(u, v);
		for (int k = 0; k < log2_n; k++) {
			if ((depth[v] - depth[u]) >> k & 1) {
				v = parent[k][v];
			}
		}
		if (u == v)
			return u;
		for (int k = log2_n - 1; k >= 0; k--) {
			if (parent[k][u] != parent[k][v]) {
				u = parent[k][u];
				v = parent[k][v];
			}
		}
		return parent[0][u];
	}
	Weight distance(int u, int v) {
		Node lca = query(u, v);
		return dist[u] + dist[v] - 2 * dist[lca];
	}
};


signed main(signed argc, char *argv[]) {
	cin.tie(0);
	ios::sync_with_stdio(false);
	cout << fixed << setprecision(12);

	int N, M; cin >> N >> M;
	int Q; cin >> Q;
	vector<int>a(M), b(M); rep(i, 0, M) { cin >> a[i] >> b[i]; a[i]--, b[i]--; }
	vector<int>v(Q), w(Q); rep(i, 0, Q) { cin >> v[i] >> w[i]; v[i]--, w[i]--; }

	Graph g(N);
	UnionFind uf(N);
	rep(i, 0, M) {
		addEdge(g, a[i], b[i]);
		uf.unite(a[i], b[i]);
	}

	vector<vector<int>>cc(N);
	rep(i, 0, N) {
		cc[uf.root(i)].eb(i);
	}

	vector<int>freq(N);
	vector<vector<pii>>query(N);
	rep(i, 0, Q) {
		if (not uf.same(v[i], w[i])) {
			freq[v[i]]++;
			freq[w[i]]++;
		}
		else {
			query[uf.root(v[i])].eb(v[i], w[i]);
		}
	}
	int ans2 = 0;
	rep(i, 0, N) {
		if (query[i].empty())continue;
		dump(i);
		auto& comp = cc[i];
		sort(all(comp));
		dump(comp.size());
		Graph gg(comp.size());
		for (auto c : comp) {
			for (auto e : g[c]) {
				if (uf.same(e.s, e.d) and e.s < e.d) {
					int p = lower_bound(all(comp), e.s) - comp.begin();
					int q = lower_bound(all(comp), e.d) - comp.begin();
					addEdge(gg, p, q);
				}
			}
		}
		dump("!!!");
		LCA lca(gg, 0);
		for (auto qq : query[i]) {
			int p = lower_bound(all(comp), qq.first) - comp.begin();
			int q = lower_bound(all(comp), qq.second) - comp.begin();
			ans2 += lca.distance(p, q);
		}
	}
	dump(ans2);
	dump(freq);
	vector<int>visited(N);
	vector<int>sum(N);
	vector<int>dp(N);
	auto dfs0 = [&](auto f, int u, int p) ->void {
		int x = freq[u];
		int z = 0;
		for (auto e : g[u]) {
			if (e.d == p)continue;
			f(f, e.d, u);
			x += sum[e.d];
			z += dp[e.d];
			z += sum[e.d];
		}
		sum[u] = x;
		dp[u] = z;
	};
	auto dfs1 = [&](auto f, int u, int p, int _sum, int z)->int {
		dump(u, p, _sum, z);
		visited[u] = 1;
		int a = 0, b = 0, c = 0;
		for (auto e : g[u]) {
			if (e.d == p)continue;
			a += dp[e.d];
			c += sum[e.d];
		}
		int tmp = a + c + z + _sum;
		dump(a, c,tmp);
		int ret = tmp;
		for (auto e : g[u]) {
			if (e.d == p)continue;
			int hoge = f(f, e.d, u, c + _sum - sum[e.d] + freq[u], tmp - dp[e.d] - sum[e.d]);
			chmin(ret, hoge);
		}
		return ret;
	};
	int ans = 0;
	rep(i, 0, N) {
		if (visited[i])continue;
		dump(i);
		dfs0(dfs0, i, -1);
		dump(sum);
		dump(dp);
		ans += dfs1(dfs1, i, -1, 0, 0);
		dump(ans);
	}
	cout << ans+ans2 << endl;




	return 0;
}
0