9114 2024. 02. 14 17:07:18 111 Bináris Sakk cpp17 Elfogadva 100/100 1.708s 311588 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 Összpont Teszt Verdikt Idő Memória
subtask1 0/0
1 Elfogadva 3ms 1892 KiB
2 Elfogadva 3ms 2088 KiB
subtask2 11/11
3 Elfogadva 2ms 2164 KiB
4 Elfogadva 3ms 2300 KiB
5 Elfogadva 3ms 2524 KiB
6 Elfogadva 3ms 2720 KiB
7 Elfogadva 3ms 2952 KiB
8 Elfogadva 4ms 4036 KiB
9 Elfogadva 4ms 4172 KiB
10 Elfogadva 4ms 4464 KiB
11 Elfogadva 4ms 4884 KiB
12 Elfogadva 4ms 4992 KiB
13 Elfogadva 4ms 5012 KiB
14 Elfogadva 4ms 5160 KiB
15 Elfogadva 4ms 5360 KiB
16 Elfogadva 4ms 5260 KiB
17 Elfogadva 4ms 5516 KiB
18 Elfogadva 3ms 4176 KiB
subtask3 19/19
19 Elfogadva 518ms 126808 KiB
20 Elfogadva 79ms 34340 KiB
21 Elfogadva 71ms 30644 KiB
22 Elfogadva 1.649s 287856 KiB
23 Elfogadva 130ms 53184 KiB
24 Elfogadva 37ms 19192 KiB
25 Elfogadva 1.327s 293908 KiB
26 Elfogadva 1.554s 294212 KiB
27 Elfogadva 1.312s 294252 KiB
28 Elfogadva 1.305s 294192 KiB
29 Elfogadva 662ms 286584 KiB
30 Elfogadva 625ms 287884 KiB
31 Elfogadva 1.324s 294452 KiB
32 Elfogadva 1.708s 293336 KiB
subtask4 19/19
33 Elfogadva 4ms 6108 KiB
34 Elfogadva 4ms 6176 KiB
35 Elfogadva 3ms 4876 KiB
36 Elfogadva 3ms 5088 KiB
37 Elfogadva 3ms 5180 KiB
38 Elfogadva 4ms 5444 KiB
39 Elfogadva 4ms 6368 KiB
40 Elfogadva 4ms 6456 KiB
41 Elfogadva 4ms 6452 KiB
42 Elfogadva 4ms 6472 KiB
43 Elfogadva 4ms 6480 KiB
44 Elfogadva 4ms 6476 KiB
45 Elfogadva 4ms 6564 KiB
46 Elfogadva 4ms 6416 KiB
47 Elfogadva 4ms 6556 KiB
subtask5 51/51
48 Elfogadva 57ms 28372 KiB
49 Elfogadva 171ms 65036 KiB
50 Elfogadva 939ms 218780 KiB
51 Elfogadva 908ms 252020 KiB
52 Elfogadva 312ms 101488 KiB
53 Elfogadva 435ms 137900 KiB
54 Elfogadva 158ms 63044 KiB
55 Elfogadva 46ms 25312 KiB
56 Elfogadva 157ms 62052 KiB
57 Elfogadva 1.103s 295996 KiB
58 Elfogadva 1.46s 302320 KiB
59 Elfogadva 1.139s 302292 KiB
60 Elfogadva 1.447s 302296 KiB
61 Elfogadva 1.172s 302432 KiB
62 Elfogadva 1.457s 302292 KiB
63 Elfogadva 657ms 311576 KiB
64 Elfogadva 569ms 311588 KiB
65 Elfogadva 660ms 298836 KiB
66 Elfogadva 652ms 298984 KiB
67 Elfogadva 1.434s 302460 KiB
68 Elfogadva 1.437s 302460 KiB