91132024-02-14 17:04:27111Bináris Sakkcpp17Time limit exceeded 81/1002.101s432628 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<set<int>> g(N * 2);
	for (int i = 0; i < N; i++) {
		g[i].insert(N + i);
		g[N + i].insert(i);
	}
	for (auto m : {m1, m2}) {
		for (auto [_, v] : m) {
			sort(v.begin(), v.end());
			for (int i = 0; i + 1 < v.size(); i++) {
				g[v[i].second].insert(v[i + 1].second);
				g[v[i + 1].second].insert(v[i].second);
			}
		}
	}
	for (auto m : {m3, m4}) {
		for (auto [_, v] : m) {
			sort(v.begin(), v.end());
			for (int i = 0; i + 1 < v.size(); i++) {
				g[N + v[i].second].insert(N + v[i + 1].second);
				g[N + v[i + 1].second].insert(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
2Accepted3ms2136 KiB
subtask211/11
3Accepted3ms2308 KiB
4Accepted3ms2520 KiB
5Accepted3ms2744 KiB
6Accepted3ms2832 KiB
7Accepted3ms2948 KiB
8Accepted4ms4412 KiB
9Accepted4ms4672 KiB
10Accepted6ms4928 KiB
11Accepted6ms5220 KiB
12Accepted6ms5400 KiB
13Accepted7ms5292 KiB
14Accepted4ms5600 KiB
15Accepted6ms5652 KiB
16Accepted4ms5628 KiB
17Accepted4ms5604 KiB
18Accepted3ms4112 KiB
subtask30/19
19Accepted973ms178956 KiB
20Accepted126ms46800 KiB
21Accepted111ms42776 KiB
22Time limit exceeded2.078s207244 KiB
23Accepted233ms74776 KiB
24Accepted52ms25644 KiB
25Time limit exceeded2.069s213308 KiB
26Time limit exceeded2.085s214080 KiB
27Accepted1.973s424464 KiB
28Time limit exceeded2.101s214244 KiB
29Accepted1.106s410684 KiB
30Accepted1.09s410800 KiB
31Time limit exceeded2.089s214280 KiB
32Time limit exceeded2.076s215768 KiB
subtask419/19
33Accepted6ms6564 KiB
34Accepted6ms6692 KiB
35Accepted3ms5068 KiB
36Accepted3ms5604 KiB
37Accepted4ms5804 KiB
38Accepted4ms6120 KiB
39Accepted6ms7176 KiB
40Accepted6ms7176 KiB
41Accepted6ms7180 KiB
42Accepted7ms7120 KiB
43Accepted6ms7288 KiB
44Accepted6ms7312 KiB
45Accepted4ms7168 KiB
46Accepted6ms7232 KiB
47Accepted6ms7184 KiB
subtask551/51
48Accepted82ms35044 KiB
49Accepted270ms80940 KiB
50Accepted1.289s273032 KiB
51Accepted1.527s318660 KiB
52Accepted499ms129112 KiB
53Accepted731ms174788 KiB
54Accepted268ms78176 KiB
55Accepted64ms30732 KiB
56Accepted245ms76740 KiB
57Accepted1.907s378300 KiB
58Accepted1.93s395940 KiB
59Accepted1.521s395944 KiB
60Accepted1.947s396044 KiB
61Accepted1.922s386684 KiB
62Accepted1.529s386580 KiB
63Accepted1.021s432564 KiB
64Accepted1.052s432628 KiB
65Accepted1.023s380612 KiB
66Accepted870ms380540 KiB
67Accepted1.906s386788 KiB
68Accepted1.912s386588 KiB