91142024-02-14 17:07:18111Bináris Sakkcpp17Accepted 100/1001.708s311588 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long

#define pii pair<int, int>

#define MOD 1000000007

int pow_mod(int x, int p, int m = MOD) {
	int r = 1;
	while (p > 0) {
		if (p % 2 == 1) {
			r *= x;
			r %= m;
		}
		p /= 2;
		x *= x;
		x %= m;
	}
	return r;
}

void scc_dfs(const auto& g, auto& v, auto& s, int i) {
	if (v[i]) {
		return;
	}
	v[i] = true;
	for (int j : g[i]) {
		scc_dfs(g, v, s, j);
	}
	s.push_back(i);
}

void scc(const auto& g, auto& h) {
	int N = g.size();
	vector<int> v;
	vector<int> s;
	v.assign(N, false);
	for (int i = 0; i < N; i++) {
		scc_dfs(g, v, s, i);
	}
	vector<vector<int>> gt(N);
	for (int i = 0; i < N; i++) {
		for (int j : g[i]) {
			gt[j].push_back(i);
		}
	}
	reverse(s.begin(), s.end());
	v.assign(N, false);
	for (int i : s) {
		if (v[i]) {
			continue;
		}
		h.emplace_back();
		scc_dfs(gt, v, h.back(), i);
	}
}

signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
#ifdef CB
	freopen("in.txt", "r", stdin);
//	freopen("out.txt", "w", stdout);
#endif
	int R, C, N;
	cin >> R >> C >> N;
	map<int, vector<pii>> m1, m2, m3, m4;
	for (int i = 0; i < N; i++) {
		int r, c;
		cin >> r >> c;
		m1[r].emplace_back(r + c, i);
		m2[c].emplace_back(r + c, i);
		m3[r + c].emplace_back(r - c, i);
		m4[r - c].emplace_back(r + c, i);
	}
	vector<vector<int>> g(N * 2);
	for (int i = 0; i < N; i++) {
		g[i].push_back(N + i);
		g[N + i].push_back(i);
	}
	for (auto& [_, v] : m1) {
		sort(v.begin(), v.end());
		for (int i = 0; i + 1 < v.size(); i++) {
			g[v[i].second].push_back(v[i + 1].second);
			g[v[i + 1].second].push_back(v[i].second);
		}
	}
	for (auto& [_, v] : m2) {
		sort(v.begin(), v.end());
		for (int i = 0; i + 1 < v.size(); i++) {
			g[v[i].second].push_back(v[i + 1].second);
			g[v[i + 1].second].push_back(v[i].second);
		}
	}
	for (auto& [_, v] : m3) {
		sort(v.begin(), v.end());
		for (int i = 0; i + 1 < v.size(); i++) {
			g[N + v[i].second].push_back(N + v[i + 1].second);
			g[N + v[i + 1].second].push_back(N + v[i].second);
		}
	}
	for (auto& [_, v] : m4) {
		sort(v.begin(), v.end());
		for (int i = 0; i + 1 < v.size(); i++) {
			g[N + v[i].second].push_back(N + v[i + 1].second);
			g[N + v[i + 1].second].push_back(N + v[i].second);
		}
	}
	vector<vector<int>> h;
	scc(g, h);
	cout << pow_mod(2, h.size()) << endl;
	return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1892 KiB
2Accepted3ms2088 KiB
subtask211/11
3Accepted2ms2164 KiB
4Accepted3ms2300 KiB
5Accepted3ms2524 KiB
6Accepted3ms2720 KiB
7Accepted3ms2952 KiB
8Accepted4ms4036 KiB
9Accepted4ms4172 KiB
10Accepted4ms4464 KiB
11Accepted4ms4884 KiB
12Accepted4ms4992 KiB
13Accepted4ms5012 KiB
14Accepted4ms5160 KiB
15Accepted4ms5360 KiB
16Accepted4ms5260 KiB
17Accepted4ms5516 KiB
18Accepted3ms4176 KiB
subtask319/19
19Accepted518ms126808 KiB
20Accepted79ms34340 KiB
21Accepted71ms30644 KiB
22Accepted1.649s287856 KiB
23Accepted130ms53184 KiB
24Accepted37ms19192 KiB
25Accepted1.327s293908 KiB
26Accepted1.554s294212 KiB
27Accepted1.312s294252 KiB
28Accepted1.305s294192 KiB
29Accepted662ms286584 KiB
30Accepted625ms287884 KiB
31Accepted1.324s294452 KiB
32Accepted1.708s293336 KiB
subtask419/19
33Accepted4ms6108 KiB
34Accepted4ms6176 KiB
35Accepted3ms4876 KiB
36Accepted3ms5088 KiB
37Accepted3ms5180 KiB
38Accepted4ms5444 KiB
39Accepted4ms6368 KiB
40Accepted4ms6456 KiB
41Accepted4ms6452 KiB
42Accepted4ms6472 KiB
43Accepted4ms6480 KiB
44Accepted4ms6476 KiB
45Accepted4ms6564 KiB
46Accepted4ms6416 KiB
47Accepted4ms6556 KiB
subtask551/51
48Accepted57ms28372 KiB
49Accepted171ms65036 KiB
50Accepted939ms218780 KiB
51Accepted908ms252020 KiB
52Accepted312ms101488 KiB
53Accepted435ms137900 KiB
54Accepted158ms63044 KiB
55Accepted46ms25312 KiB
56Accepted157ms62052 KiB
57Accepted1.103s295996 KiB
58Accepted1.46s302320 KiB
59Accepted1.139s302292 KiB
60Accepted1.447s302296 KiB
61Accepted1.172s302432 KiB
62Accepted1.457s302292 KiB
63Accepted657ms311576 KiB
64Accepted569ms311588 KiB
65Accepted660ms298836 KiB
66Accepted652ms298984 KiB
67Accepted1.434s302460 KiB
68Accepted1.437s302460 KiB