65522023-12-09 01:09:35RRoliBináris Sakkcpp17Runtime error 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted3ms1928 KiB
2Runtime error3ms2312 KiB
subtask20/11
3Accepted3ms2536 KiB
4Runtime error3ms2828 KiB
5Accepted3ms2920 KiB
6Runtime error3ms2960 KiB
7Accepted3ms3076 KiB
8Accepted3ms3996 KiB
9Runtime error4ms4300 KiB
10Accepted4ms3936 KiB
11Accepted4ms4608 KiB
12Runtime error4ms4708 KiB
13Accepted4ms4720 KiB
14Accepted28ms4676 KiB
15Accepted28ms4856 KiB
16Accepted28ms5096 KiB
17Accepted28ms5412 KiB
18Accepted3ms5180 KiB
subtask30/19
19Accepted794ms49556 KiB
20Accepted282ms15732 KiB
21Accepted43ms14600 KiB
22Time limit exceeded2.104s55984 KiB
23Accepted537ms22280 KiB
24Accepted23ms9984 KiB
25Time limit exceeded2.101s57968 KiB
26Time limit exceeded2.059s58120 KiB
27Time limit exceeded2.002s112912 KiB
28Time limit exceeded2.065s57976 KiB
29Time limit exceeded2.062s58288 KiB
30Accepted1.592s113124 KiB
31Time limit exceeded2.025s113348 KiB
32Time limit exceeded2.078s58180 KiB
subtask40/19
33Runtime error174ms522000 KiB
34Runtime error170ms521992 KiB
35Runtime error211ms521968 KiB
36Runtime error168ms521940 KiB
37Runtime error168ms521936 KiB
38Runtime error217ms521916 KiB
39Runtime error179ms521892 KiB
40Runtime error222ms521736 KiB
41Runtime error175ms521736 KiB
42Runtime error218ms521732 KiB
43Runtime error173ms521724 KiB
44Runtime error171ms521708 KiB
45Runtime error167ms521676 KiB
46Runtime error189ms521612 KiB
47Runtime error188ms521596 KiB
subtask50/51
48Runtime error215ms521596 KiB
49Runtime error215ms521588 KiB
50Runtime error216ms521592 KiB
51Runtime error174ms521572 KiB
52Runtime error173ms521572 KiB
53Runtime error222ms521568 KiB
54Runtime error172ms521576 KiB
55Runtime error218ms521560 KiB
56Runtime error218ms521564 KiB
57Runtime error172ms521548 KiB
58Runtime error217ms521564 KiB
59Runtime error173ms521544 KiB
60Runtime error170ms521516 KiB
61Runtime error214ms521532 KiB
62Runtime error216ms521536 KiB
63Runtime error216ms521512 KiB
64Runtime error168ms521520 KiB
65Runtime error219ms521520 KiB
66Runtime error209ms521524 KiB
67Runtime error219ms521380 KiB
68Runtime error219ms521384 KiB