91142024-02-14 17:07:18111Bináris Sakkcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1892 KiB
2Elfogadva3ms2088 KiB
subtask211/11
3Elfogadva2ms2164 KiB
4Elfogadva3ms2300 KiB
5Elfogadva3ms2524 KiB
6Elfogadva3ms2720 KiB
7Elfogadva3ms2952 KiB
8Elfogadva4ms4036 KiB
9Elfogadva4ms4172 KiB
10Elfogadva4ms4464 KiB
11Elfogadva4ms4884 KiB
12Elfogadva4ms4992 KiB
13Elfogadva4ms5012 KiB
14Elfogadva4ms5160 KiB
15Elfogadva4ms5360 KiB
16Elfogadva4ms5260 KiB
17Elfogadva4ms5516 KiB
18Elfogadva3ms4176 KiB
subtask319/19
19Elfogadva518ms126808 KiB
20Elfogadva79ms34340 KiB
21Elfogadva71ms30644 KiB
22Elfogadva1.649s287856 KiB
23Elfogadva130ms53184 KiB
24Elfogadva37ms19192 KiB
25Elfogadva1.327s293908 KiB
26Elfogadva1.554s294212 KiB
27Elfogadva1.312s294252 KiB
28Elfogadva1.305s294192 KiB
29Elfogadva662ms286584 KiB
30Elfogadva625ms287884 KiB
31Elfogadva1.324s294452 KiB
32Elfogadva1.708s293336 KiB
subtask419/19
33Elfogadva4ms6108 KiB
34Elfogadva4ms6176 KiB
35Elfogadva3ms4876 KiB
36Elfogadva3ms5088 KiB
37Elfogadva3ms5180 KiB
38Elfogadva4ms5444 KiB
39Elfogadva4ms6368 KiB
40Elfogadva4ms6456 KiB
41Elfogadva4ms6452 KiB
42Elfogadva4ms6472 KiB
43Elfogadva4ms6480 KiB
44Elfogadva4ms6476 KiB
45Elfogadva4ms6564 KiB
46Elfogadva4ms6416 KiB
47Elfogadva4ms6556 KiB
subtask551/51
48Elfogadva57ms28372 KiB
49Elfogadva171ms65036 KiB
50Elfogadva939ms218780 KiB
51Elfogadva908ms252020 KiB
52Elfogadva312ms101488 KiB
53Elfogadva435ms137900 KiB
54Elfogadva158ms63044 KiB
55Elfogadva46ms25312 KiB
56Elfogadva157ms62052 KiB
57Elfogadva1.103s295996 KiB
58Elfogadva1.46s302320 KiB
59Elfogadva1.139s302292 KiB
60Elfogadva1.447s302296 KiB
61Elfogadva1.172s302432 KiB
62Elfogadva1.457s302292 KiB
63Elfogadva657ms311576 KiB
64Elfogadva569ms311588 KiB
65Elfogadva660ms298836 KiB
66Elfogadva652ms298984 KiB
67Elfogadva1.434s302460 KiB
68Elfogadva1.437s302460 KiB