65532023-12-09 01:25:14RRoliBináris Sakkcpp17Time limit exceeded 30/1002.099s7164 KiB
#include <bits/stdc++.h>
using namespace std;

int R, C, N;
vector<int> szulo, meret;
vector<pair<int, int>> koord;

int find(int k) {
	if(szulo[k] == k) return k;
	return szulo[k] = find(szulo[k]);
}

bool unio(int a, int b) {
	a = find(a);
	b = find(b);

	if(a == b) return true;

	if(meret[a] >= meret[b]) {
		meret[a] += meret[b];
		szulo[b] = a;
	} else {
		meret[b] += meret[a];
		szulo[a] = b;
	}
	return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> R >> C >> N;

	szulo.resize(N+1);
	meret.resize(N+1);
	koord.resize(N+1);

	for(int i = 1; i <= N; i++) {
		szulo[i] = i;
		meret[i] = 1;
	}

    for(int i = 1; i <= N; i++) {
		int r, c;
		cin >> r >> c;
		koord[i] = make_pair(r, c);
	}

	for(int i = 1; i < N; i++) {
		for(int j = i+1; j <= N; j++) {
			if(koord[i].first == koord[j].first || koord[i].second == koord[j].second ||
			abs(koord[i].first-koord[j].first) == abs(koord[i].second-koord[j].second))
				unio(i, j);
		}
	}

	int p = 0;
	for(int i = 1; i <= N; i++) if(find(i) == i) p++;
	int ans = 1;
    while(p > 0) {
        ans = (ans * 2) % 1000000007;
        p--;
    }
    cout << ans << '\n';

    return 0;
}

SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms2036 KiB
2Accepted3ms2200 KiB
subtask211/11
3Accepted3ms2424 KiB
4Accepted3ms2576 KiB
5Accepted3ms2768 KiB
6Accepted3ms2976 KiB
7Accepted3ms3196 KiB
8Accepted3ms3416 KiB
9Accepted3ms3480 KiB
10Accepted4ms3604 KiB
11Accepted4ms3944 KiB
12Accepted4ms3900 KiB
13Accepted4ms3896 KiB
14Accepted6ms3892 KiB
15Accepted6ms4024 KiB
16Accepted6ms4108 KiB
17Accepted7ms4304 KiB
18Accepted3ms4176 KiB
subtask30/19
19Time limit exceeded2.065s4712 KiB
20Accepted801ms4848 KiB
21Accepted564ms4908 KiB
22Time limit exceeded2.046s6604 KiB
23Accepted1.983s5456 KiB
24Accepted203ms5012 KiB
25Time limit exceeded2.099s6876 KiB
26Time limit exceeded2.053s6868 KiB
27Time limit exceeded2.062s6880 KiB
28Time limit exceeded2.066s6884 KiB
29Time limit exceeded2.063s7164 KiB
30Time limit exceeded2.059s6864 KiB
31Time limit exceeded2.071s6920 KiB
32Time limit exceeded2.062s6900 KiB
subtask419/19
33Accepted4ms4656 KiB
34Accepted4ms4752 KiB
35Accepted3ms4704 KiB
36Accepted3ms4724 KiB
37Accepted3ms4728 KiB
38Accepted3ms4820 KiB
39Accepted4ms4840 KiB
40Accepted4ms4740 KiB
41Accepted4ms4740 KiB
42Accepted4ms4744 KiB
43Accepted6ms4740 KiB
44Accepted6ms4896 KiB
45Accepted7ms4740 KiB
46Accepted7ms4652 KiB
47Accepted4ms4728 KiB
subtask50/51
48Accepted421ms5052 KiB
49Time limit exceeded2.085s4412 KiB
50Time limit exceeded2.069s6116 KiB
51Time limit exceeded2.042s6320 KiB
52Time limit exceeded2.078s4916 KiB
53Time limit exceeded2.069s5248 KiB
54Time limit exceeded2.065s4632 KiB
55Accepted314ms4912 KiB
56Time limit exceeded2.072s4476 KiB
57Time limit exceeded2.065s6904 KiB
58Time limit exceeded2.053s6804 KiB
59Time limit exceeded2.049s6984 KiB
60Time limit exceeded2.062s6904 KiB
61Time limit exceeded2.085s6920 KiB
62Time limit exceeded2.073s7060 KiB
63Time limit exceeded2.085s6844 KiB
64Time limit exceeded2.062s6912 KiB
65Time limit exceeded2.058s6844 KiB
66Time limit exceeded2.062s7056 KiB
67Time limit exceeded2.046s7056 KiB
68Time limit exceeded2.049s6972 KiB