110062024-06-04 12:06:13zsomborÚtvonalakcpp17Wrong answer 0/100681ms78992 KiB
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int n, m, q;
vector <vector <int>> g(2e5);

vector <int> p(2e5, 0);
vector <int> d(2e5, 0);
vector <int> l(2e5, 0);
vector <bool> cut(2e5, false);
stack <int> s;
vector <vector <int>> bcc;

int k;
vector <int> comp(2e5, -1);
vector <vector <int>> t(3e5);

vector <int> D(3e5, 0);
vector <vector <int>> up(3e5, vector <int>(20, 0));
vector <int> w(3e5, 1);
vector <int> wsum(3e5, -1);

void dfs(int x) {
	s.push(x);
	for (int i : g[x]) {
		if (p[x] == i) continue;
		if (p[i] && d[i] > d[x]) continue;
		if (p[i] && d[i] < d[x]) { l[x] = min(l[x], d[i]); continue; }

		p[i] = x;
		d[i] = l[i] = d[x] + 1;
		dfs(i);
		l[x] = min(l[x], l[i]);

		if (l[i] >= d[x]) {
			cut[x] = true;
			vector <int> v;
			while (l[s.top()] >= d[x]) { v.push_back(s.top()); s.pop(); }
			v.push_back(x);
			bcc.push_back(v);
		}
	}
}

void dfs2(int x) {
	for (int i : t[x]) {
		if (up[x][0] == i) continue;
		D[i] = D[x] + 1;
		up[i][0] = x;
		wsum[i] += wsum[x] + w[i];
		dfs2(i);
	}
}

int lca(int a, int b) {
	if (D[a] < D[b]) swap(a, b);
	for (int j = 19; j >= 0; j--) {
		if (D[up[a][j]] >= D[b]) a = up[a][j];
	}
	if (a == b) return a;
	for (int j = 19; j >= 0; j--) {
		if (up[a][j] == up[b][j]) continue;
		a = up[a][j];
		b = up[b][j];
	}
	return up[a][0];
}

void solve() {
	int a, b, c;
	cin >> a >> b;
	a = comp[a]; b = comp[b];
	c = lca(a, b);
	//cout << a << " " << b << " " << c << endl;
	//cout << wsum[a] << " " << wsum[b] << " " << wsum[c] << "\n";
	cout << wsum[a] + wsum[b] - 2 * wsum[c] + w[c] - 2 << "\n";
}

int main() {
	cin >> n >> m >> q;
	int a, b;
	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		g[a].push_back(b);
		g[b].push_back(a);
	}

	p[1] = l[1] = -1;
	dfs(1);
	int cnt = 0;
	for (int i : g[1]) if (p[i] == 1) cnt++;
	if (cnt < 2) cut[1] = false;

	/*cout << "\n";
	for (int i = 1; i <= n; i++) if (cut[i]) cout << i << " ";
	cout << "\n\n";
	for (auto v : bcc) {
		for (int i : v) cout << i << " ";
		cout << "\n";
	}
	cout << "\n";*/

	k = bcc.size();
	for (int i = 0; i < bcc.size(); i++) {
		for (int x : bcc[i]) {
			if (!cut[x]) { comp[x] = i; continue; }
			if (comp[x] == -1) comp[x] = k++;
			t[i].push_back(comp[x]);
			t[comp[x]].push_back(i);
		}
	}

	for (int i = 0; i < bcc.size(); i++) w[i] = bcc[i].size();
	wsum[0] = w[0];
	dfs2(0);
	for (int j = 1; j < 20; j++) {
		for (int i = 0; i < k; i++) {
			up[i][j] = up[up[i][j - 1]][j - 1];
		}
	}
	while (q--) solve();
}

/*

10 13 4
1 8
1 10
10 9
9 8
8 10
8 6
8 7
7 5
6 5
5 4
6 3
3 2
2 6
8 10
1 7
4 5
6 4

*/
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted54ms53988 KiB
2Wrong answer243ms58768 KiB
subtask20/15
3Wrong answer56ms54040 KiB
4Wrong answer67ms54284 KiB
5Wrong answer75ms55012 KiB
6Wrong answer75ms54652 KiB
7Wrong answer136ms56568 KiB
8Wrong answer193ms58876 KiB
subtask30/15
9Wrong answer56ms54116 KiB
10Wrong answer67ms54288 KiB
11Wrong answer67ms54884 KiB
12Wrong answer81ms55392 KiB
13Wrong answer172ms60868 KiB
14Wrong answer358ms67648 KiB
15Wrong answer666ms75544 KiB
subtask40/15
16Wrong answer70ms54196 KiB
17Wrong answer68ms54268 KiB
18Wrong answer79ms54544 KiB
19Wrong answer142ms56440 KiB
20Wrong answer239ms58844 KiB
subtask50/15
21Wrong answer67ms54048 KiB
22Wrong answer65ms54024 KiB
23Wrong answer68ms54244 KiB
24Wrong answer57ms54032 KiB
25Wrong answer65ms54116 KiB
26Wrong answer64ms54116 KiB
subtask60/40
27Accepted54ms53988 KiB
28Wrong answer287ms58788 KiB
29Wrong answer56ms54040 KiB
30Wrong answer67ms54284 KiB
31Wrong answer75ms55012 KiB
32Wrong answer75ms54652 KiB
33Wrong answer136ms56568 KiB
34Wrong answer193ms58876 KiB
35Wrong answer56ms54116 KiB
36Wrong answer67ms54288 KiB
37Wrong answer67ms54884 KiB
38Wrong answer81ms55392 KiB
39Wrong answer172ms60868 KiB
40Wrong answer358ms67648 KiB
41Wrong answer666ms75544 KiB
42Wrong answer70ms54196 KiB
43Wrong answer68ms54268 KiB
44Wrong answer79ms54544 KiB
45Wrong answer142ms56440 KiB
46Wrong answer239ms58844 KiB
47Wrong answer67ms54048 KiB
48Wrong answer65ms54024 KiB
49Wrong answer68ms54244 KiB
50Wrong answer57ms54032 KiB
51Wrong answer65ms54116 KiB
52Wrong answer64ms54116 KiB
53Wrong answer485ms77040 KiB
54Wrong answer70ms54176 KiB
55Wrong answer68ms55012 KiB
56Wrong answer111ms54540 KiB
57Wrong answer312ms56640 KiB
58Wrong answer194ms57000 KiB
59Wrong answer670ms78992 KiB
60Wrong answer681ms59188 KiB
61Wrong answer661ms59252 KiB
62Wrong answer672ms59244 KiB