65522023-12-09 01:09:35RRoliBináris Sakkcpp17Futási hiba 0/1002.104s522000 KiB
#include <bits/stdc++.h>
using namespace std;

int R, C, N;
vector<int> szulo, meret;
vector<set<int>> sor, osz, atl, foa;
vector<pair<bool, 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;
}

void keres(int k) {
	koord[k].first = false;

	sor[koord[k].second.first].erase(k);
	osz[koord[k].second.second].erase(k);
	atl[koord[k].second.first-koord[k].second.second+C].erase(k);
	foa[koord[k].second.first+koord[k].second.second].erase(k);

	for(int i : sor[koord[k].second.first]) {
		unio(k, i);
		keres(i);
	}
	for(int i : osz[koord[k].second.second]) {
		unio(k, i);
		keres(i);
	}
	for(int i : atl[koord[k].second.first-koord[k].second.second+C]) {
		unio(k, i);
		keres(i);
	}
	for(int i : foa[koord[k].second.first+koord[k].second.second]) {
		unio(k, i);
		keres(i);
	}
}

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);
	sor.resize(R+1);
	osz.resize(C+1);
	atl.resize(R+C+1);
	foa.resize(R+C+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(true, make_pair(r, c));

		sor[r].insert(i);
		osz[c].insert(i);
		atl[r-c+C].insert(i);
		foa[r+c].insert(i);
	}

	for(int i = 1; i <= N; i++) {
		if(koord[i].first) keres(i);
	}

	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
1Elfogadva3ms1928 KiB
2Futási hiba3ms2312 KiB
subtask20/11
3Elfogadva3ms2536 KiB
4Futási hiba3ms2828 KiB
5Elfogadva3ms2920 KiB
6Futási hiba3ms2960 KiB
7Elfogadva3ms3076 KiB
8Elfogadva3ms3996 KiB
9Futási hiba4ms4300 KiB
10Elfogadva4ms3936 KiB
11Elfogadva4ms4608 KiB
12Futási hiba4ms4708 KiB
13Elfogadva4ms4720 KiB
14Elfogadva28ms4676 KiB
15Elfogadva28ms4856 KiB
16Elfogadva28ms5096 KiB
17Elfogadva28ms5412 KiB
18Elfogadva3ms5180 KiB
subtask30/19
19Elfogadva794ms49556 KiB
20Elfogadva282ms15732 KiB
21Elfogadva43ms14600 KiB
22Időlimit túllépés2.104s55984 KiB
23Elfogadva537ms22280 KiB
24Elfogadva23ms9984 KiB
25Időlimit túllépés2.101s57968 KiB
26Időlimit túllépés2.059s58120 KiB
27Időlimit túllépés2.002s112912 KiB
28Időlimit túllépés2.065s57976 KiB
29Időlimit túllépés2.062s58288 KiB
30Elfogadva1.592s113124 KiB
31Időlimit túllépés2.025s113348 KiB
32Időlimit túllépés2.078s58180 KiB
subtask40/19
33Futási hiba174ms522000 KiB
34Futási hiba170ms521992 KiB
35Futási hiba211ms521968 KiB
36Futási hiba168ms521940 KiB
37Futási hiba168ms521936 KiB
38Futási hiba217ms521916 KiB
39Futási hiba179ms521892 KiB
40Futási hiba222ms521736 KiB
41Futási hiba175ms521736 KiB
42Futási hiba218ms521732 KiB
43Futási hiba173ms521724 KiB
44Futási hiba171ms521708 KiB
45Futási hiba167ms521676 KiB
46Futási hiba189ms521612 KiB
47Futási hiba188ms521596 KiB
subtask50/51
48Futási hiba215ms521596 KiB
49Futási hiba215ms521588 KiB
50Futási hiba216ms521592 KiB
51Futási hiba174ms521572 KiB
52Futási hiba173ms521572 KiB
53Futási hiba222ms521568 KiB
54Futási hiba172ms521576 KiB
55Futási hiba218ms521560 KiB
56Futási hiba218ms521564 KiB
57Futási hiba172ms521548 KiB
58Futási hiba217ms521564 KiB
59Futási hiba173ms521544 KiB
60Futási hiba170ms521516 KiB
61Futási hiba214ms521532 KiB
62Futási hiba216ms521536 KiB
63Futási hiba216ms521512 KiB
64Futási hiba168ms521520 KiB
65Futási hiba219ms521520 KiB
66Futási hiba209ms521524 KiB
67Futási hiba219ms521380 KiB
68Futási hiba219ms521384 KiB