91132024-02-14 17:04:27111Bináris Sakkcpp17Időlimit túllépés 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1892 KiB
2Elfogadva3ms2136 KiB
subtask211/11
3Elfogadva3ms2308 KiB
4Elfogadva3ms2520 KiB
5Elfogadva3ms2744 KiB
6Elfogadva3ms2832 KiB
7Elfogadva3ms2948 KiB
8Elfogadva4ms4412 KiB
9Elfogadva4ms4672 KiB
10Elfogadva6ms4928 KiB
11Elfogadva6ms5220 KiB
12Elfogadva6ms5400 KiB
13Elfogadva7ms5292 KiB
14Elfogadva4ms5600 KiB
15Elfogadva6ms5652 KiB
16Elfogadva4ms5628 KiB
17Elfogadva4ms5604 KiB
18Elfogadva3ms4112 KiB
subtask30/19
19Elfogadva973ms178956 KiB
20Elfogadva126ms46800 KiB
21Elfogadva111ms42776 KiB
22Időlimit túllépés2.078s207244 KiB
23Elfogadva233ms74776 KiB
24Elfogadva52ms25644 KiB
25Időlimit túllépés2.069s213308 KiB
26Időlimit túllépés2.085s214080 KiB
27Elfogadva1.973s424464 KiB
28Időlimit túllépés2.101s214244 KiB
29Elfogadva1.106s410684 KiB
30Elfogadva1.09s410800 KiB
31Időlimit túllépés2.089s214280 KiB
32Időlimit túllépés2.076s215768 KiB
subtask419/19
33Elfogadva6ms6564 KiB
34Elfogadva6ms6692 KiB
35Elfogadva3ms5068 KiB
36Elfogadva3ms5604 KiB
37Elfogadva4ms5804 KiB
38Elfogadva4ms6120 KiB
39Elfogadva6ms7176 KiB
40Elfogadva6ms7176 KiB
41Elfogadva6ms7180 KiB
42Elfogadva7ms7120 KiB
43Elfogadva6ms7288 KiB
44Elfogadva6ms7312 KiB
45Elfogadva4ms7168 KiB
46Elfogadva6ms7232 KiB
47Elfogadva6ms7184 KiB
subtask551/51
48Elfogadva82ms35044 KiB
49Elfogadva270ms80940 KiB
50Elfogadva1.289s273032 KiB
51Elfogadva1.527s318660 KiB
52Elfogadva499ms129112 KiB
53Elfogadva731ms174788 KiB
54Elfogadva268ms78176 KiB
55Elfogadva64ms30732 KiB
56Elfogadva245ms76740 KiB
57Elfogadva1.907s378300 KiB
58Elfogadva1.93s395940 KiB
59Elfogadva1.521s395944 KiB
60Elfogadva1.947s396044 KiB
61Elfogadva1.922s386684 KiB
62Elfogadva1.529s386580 KiB
63Elfogadva1.021s432564 KiB
64Elfogadva1.052s432628 KiB
65Elfogadva1.023s380612 KiB
66Elfogadva870ms380540 KiB
67Elfogadva1.906s386788 KiB
68Elfogadva1.912s386588 KiB