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

RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva3ms2036 KiB
2Elfogadva3ms2200 KiB
subtask211/11
3Elfogadva3ms2424 KiB
4Elfogadva3ms2576 KiB
5Elfogadva3ms2768 KiB
6Elfogadva3ms2976 KiB
7Elfogadva3ms3196 KiB
8Elfogadva3ms3416 KiB
9Elfogadva3ms3480 KiB
10Elfogadva4ms3604 KiB
11Elfogadva4ms3944 KiB
12Elfogadva4ms3900 KiB
13Elfogadva4ms3896 KiB
14Elfogadva6ms3892 KiB
15Elfogadva6ms4024 KiB
16Elfogadva6ms4108 KiB
17Elfogadva7ms4304 KiB
18Elfogadva3ms4176 KiB
subtask30/19
19Időlimit túllépés2.065s4712 KiB
20Elfogadva801ms4848 KiB
21Elfogadva564ms4908 KiB
22Időlimit túllépés2.046s6604 KiB
23Elfogadva1.983s5456 KiB
24Elfogadva203ms5012 KiB
25Időlimit túllépés2.099s6876 KiB
26Időlimit túllépés2.053s6868 KiB
27Időlimit túllépés2.062s6880 KiB
28Időlimit túllépés2.066s6884 KiB
29Időlimit túllépés2.063s7164 KiB
30Időlimit túllépés2.059s6864 KiB
31Időlimit túllépés2.071s6920 KiB
32Időlimit túllépés2.062s6900 KiB
subtask419/19
33Elfogadva4ms4656 KiB
34Elfogadva4ms4752 KiB
35Elfogadva3ms4704 KiB
36Elfogadva3ms4724 KiB
37Elfogadva3ms4728 KiB
38Elfogadva3ms4820 KiB
39Elfogadva4ms4840 KiB
40Elfogadva4ms4740 KiB
41Elfogadva4ms4740 KiB
42Elfogadva4ms4744 KiB
43Elfogadva6ms4740 KiB
44Elfogadva6ms4896 KiB
45Elfogadva7ms4740 KiB
46Elfogadva7ms4652 KiB
47Elfogadva4ms4728 KiB
subtask50/51
48Elfogadva421ms5052 KiB
49Időlimit túllépés2.085s4412 KiB
50Időlimit túllépés2.069s6116 KiB
51Időlimit túllépés2.042s6320 KiB
52Időlimit túllépés2.078s4916 KiB
53Időlimit túllépés2.069s5248 KiB
54Időlimit túllépés2.065s4632 KiB
55Elfogadva314ms4912 KiB
56Időlimit túllépés2.072s4476 KiB
57Időlimit túllépés2.065s6904 KiB
58Időlimit túllépés2.053s6804 KiB
59Időlimit túllépés2.049s6984 KiB
60Időlimit túllépés2.062s6904 KiB
61Időlimit túllépés2.085s6920 KiB
62Időlimit túllépés2.073s7060 KiB
63Időlimit túllépés2.085s6844 KiB
64Időlimit túllépés2.062s6912 KiB
65Időlimit túllépés2.058s6844 KiB
66Időlimit túllépés2.062s7056 KiB
67Időlimit túllépés2.046s7056 KiB
68Időlimit túllépés2.049s6972 KiB