65542023-12-09 01:29:53RRoliBináris Sakkcpp17Időlimit túllépés 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;
}

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms1892 KiB
2Elfogadva3ms2116 KiB
subtask211/11
3Elfogadva3ms2168 KiB
4Elfogadva3ms2292 KiB
5Elfogadva3ms2524 KiB
6Elfogadva3ms2760 KiB
7Elfogadva3ms2948 KiB
8Elfogadva4ms3284 KiB
9Elfogadva4ms3408 KiB
10Elfogadva4ms3500 KiB
11Elfogadva6ms3724 KiB
12Elfogadva6ms3936 KiB
13Elfogadva6ms4020 KiB
14Elfogadva6ms4028 KiB
15Elfogadva6ms4288 KiB
16Elfogadva6ms4368 KiB
17Elfogadva6ms4368 KiB
18Elfogadva3ms4576 KiB
subtask30/19
19Időlimit túllépés2.099s5188 KiB
20Elfogadva1.225s5248 KiB
21Elfogadva952ms4932 KiB
22Időlimit túllépés2.051s6960 KiB
23Időlimit túllépés2.058s4348 KiB
24Elfogadva303ms4904 KiB
25Időlimit túllépés2.051s6904 KiB
26Időlimit túllépés2.053s6940 KiB
27Időlimit túllépés2.046s6812 KiB
28Időlimit túllépés2.078s6812 KiB
29Időlimit túllépés2.058s6900 KiB
30Időlimit túllépés2.053s7128 KiB
31Időlimit túllépés2.062s7020 KiB
32Időlimit túllépés2.069s7072 KiB
subtask419/19
33Elfogadva4ms5088 KiB
34Elfogadva4ms5040 KiB
35Elfogadva3ms5104 KiB
36Elfogadva3ms5128 KiB
37Elfogadva3ms5244 KiB
38Elfogadva3ms5328 KiB
39Elfogadva4ms5324 KiB
40Elfogadva4ms5228 KiB
41Elfogadva4ms5232 KiB
42Elfogadva4ms5272 KiB
43Elfogadva6ms5240 KiB
44Elfogadva6ms5492 KiB
45Elfogadva6ms5340 KiB
46Elfogadva6ms5336 KiB
47Elfogadva4ms5332 KiB
subtask50/51
48Elfogadva442ms5736 KiB
49Időlimit túllépés2.062s5020 KiB
50Időlimit túllépés2.062s6720 KiB
51Időlimit túllépés2.058s6984 KiB
52Időlimit túllépés2.059s5544 KiB
53Időlimit túllépés2.062s5924 KiB
54Időlimit túllépés2.075s5060 KiB
55Elfogadva328ms5644 KiB
56Időlimit túllépés2.071s4876 KiB
57Időlimit túllépés2.046s7512 KiB
58Időlimit túllépés2.073s7600 KiB
59Időlimit túllépés2.058s7560 KiB
60Időlimit túllépés2.042s7516 KiB
61Időlimit túllépés2.062s7496 KiB
62Időlimit túllépés2.062s7540 KiB
63Időlimit túllépés2.073s7472 KiB
64Időlimit túllépés2.066s7512 KiB
65Időlimit túllépés2.062s7536 KiB
66Időlimit túllépés2.053s7604 KiB
67Időlimit túllépés2.078s7668 KiB
68Időlimit túllépés2.062s7656 KiB