65542023-12-09 01:29:53RRoliBináris Sakkcpp17Time limit exceeded 30/1002.099s7668 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(find(i) != find(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
1Accepted3ms1892 KiB
2Accepted3ms2116 KiB
subtask211/11
3Accepted3ms2168 KiB
4Accepted3ms2292 KiB
5Accepted3ms2524 KiB
6Accepted3ms2760 KiB
7Accepted3ms2948 KiB
8Accepted4ms3284 KiB
9Accepted4ms3408 KiB
10Accepted4ms3500 KiB
11Accepted6ms3724 KiB
12Accepted6ms3936 KiB
13Accepted6ms4020 KiB
14Accepted6ms4028 KiB
15Accepted6ms4288 KiB
16Accepted6ms4368 KiB
17Accepted6ms4368 KiB
18Accepted3ms4576 KiB
subtask30/19
19Time limit exceeded2.099s5188 KiB
20Accepted1.225s5248 KiB
21Accepted952ms4932 KiB
22Time limit exceeded2.051s6960 KiB
23Time limit exceeded2.058s4348 KiB
24Accepted303ms4904 KiB
25Time limit exceeded2.051s6904 KiB
26Time limit exceeded2.053s6940 KiB
27Time limit exceeded2.046s6812 KiB
28Time limit exceeded2.078s6812 KiB
29Time limit exceeded2.058s6900 KiB
30Time limit exceeded2.053s7128 KiB
31Time limit exceeded2.062s7020 KiB
32Time limit exceeded2.069s7072 KiB
subtask419/19
33Accepted4ms5088 KiB
34Accepted4ms5040 KiB
35Accepted3ms5104 KiB
36Accepted3ms5128 KiB
37Accepted3ms5244 KiB
38Accepted3ms5328 KiB
39Accepted4ms5324 KiB
40Accepted4ms5228 KiB
41Accepted4ms5232 KiB
42Accepted4ms5272 KiB
43Accepted6ms5240 KiB
44Accepted6ms5492 KiB
45Accepted6ms5340 KiB
46Accepted6ms5336 KiB
47Accepted4ms5332 KiB
subtask50/51
48Accepted442ms5736 KiB
49Time limit exceeded2.062s5020 KiB
50Time limit exceeded2.062s6720 KiB
51Time limit exceeded2.058s6984 KiB
52Time limit exceeded2.059s5544 KiB
53Time limit exceeded2.062s5924 KiB
54Time limit exceeded2.075s5060 KiB
55Accepted328ms5644 KiB
56Time limit exceeded2.071s4876 KiB
57Time limit exceeded2.046s7512 KiB
58Time limit exceeded2.073s7600 KiB
59Time limit exceeded2.058s7560 KiB
60Time limit exceeded2.042s7516 KiB
61Time limit exceeded2.062s7496 KiB
62Time limit exceeded2.062s7540 KiB
63Time limit exceeded2.073s7472 KiB
64Time limit exceeded2.066s7512 KiB
65Time limit exceeded2.062s7536 KiB
66Time limit exceeded2.053s7604 KiB
67Time limit exceeded2.078s7668 KiB
68Time limit exceeded2.062s7656 KiB