6552 | 2023-12-09 01:09:35 | RRoli | Bináris Sakk | cpp17 | Futási hiba 0/100 | 2.104s | 522000 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 | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1928 KiB | ||||
2 | Futási hiba | 3ms | 2312 KiB | ||||
subtask2 | 0/11 | ||||||
3 | Elfogadva | 3ms | 2536 KiB | ||||
4 | Futási hiba | 3ms | 2828 KiB | ||||
5 | Elfogadva | 3ms | 2920 KiB | ||||
6 | Futási hiba | 3ms | 2960 KiB | ||||
7 | Elfogadva | 3ms | 3076 KiB | ||||
8 | Elfogadva | 3ms | 3996 KiB | ||||
9 | Futási hiba | 4ms | 4300 KiB | ||||
10 | Elfogadva | 4ms | 3936 KiB | ||||
11 | Elfogadva | 4ms | 4608 KiB | ||||
12 | Futási hiba | 4ms | 4708 KiB | ||||
13 | Elfogadva | 4ms | 4720 KiB | ||||
14 | Elfogadva | 28ms | 4676 KiB | ||||
15 | Elfogadva | 28ms | 4856 KiB | ||||
16 | Elfogadva | 28ms | 5096 KiB | ||||
17 | Elfogadva | 28ms | 5412 KiB | ||||
18 | Elfogadva | 3ms | 5180 KiB | ||||
subtask3 | 0/19 | ||||||
19 | Elfogadva | 794ms | 49556 KiB | ||||
20 | Elfogadva | 282ms | 15732 KiB | ||||
21 | Elfogadva | 43ms | 14600 KiB | ||||
22 | Időlimit túllépés | 2.104s | 55984 KiB | ||||
23 | Elfogadva | 537ms | 22280 KiB | ||||
24 | Elfogadva | 23ms | 9984 KiB | ||||
25 | Időlimit túllépés | 2.101s | 57968 KiB | ||||
26 | Időlimit túllépés | 2.059s | 58120 KiB | ||||
27 | Időlimit túllépés | 2.002s | 112912 KiB | ||||
28 | Időlimit túllépés | 2.065s | 57976 KiB | ||||
29 | Időlimit túllépés | 2.062s | 58288 KiB | ||||
30 | Elfogadva | 1.592s | 113124 KiB | ||||
31 | Időlimit túllépés | 2.025s | 113348 KiB | ||||
32 | Időlimit túllépés | 2.078s | 58180 KiB | ||||
subtask4 | 0/19 | ||||||
33 | Futási hiba | 174ms | 522000 KiB | ||||
34 | Futási hiba | 170ms | 521992 KiB | ||||
35 | Futási hiba | 211ms | 521968 KiB | ||||
36 | Futási hiba | 168ms | 521940 KiB | ||||
37 | Futási hiba | 168ms | 521936 KiB | ||||
38 | Futási hiba | 217ms | 521916 KiB | ||||
39 | Futási hiba | 179ms | 521892 KiB | ||||
40 | Futási hiba | 222ms | 521736 KiB | ||||
41 | Futási hiba | 175ms | 521736 KiB | ||||
42 | Futási hiba | 218ms | 521732 KiB | ||||
43 | Futási hiba | 173ms | 521724 KiB | ||||
44 | Futási hiba | 171ms | 521708 KiB | ||||
45 | Futási hiba | 167ms | 521676 KiB | ||||
46 | Futási hiba | 189ms | 521612 KiB | ||||
47 | Futási hiba | 188ms | 521596 KiB | ||||
subtask5 | 0/51 | ||||||
48 | Futási hiba | 215ms | 521596 KiB | ||||
49 | Futási hiba | 215ms | 521588 KiB | ||||
50 | Futási hiba | 216ms | 521592 KiB | ||||
51 | Futási hiba | 174ms | 521572 KiB | ||||
52 | Futási hiba | 173ms | 521572 KiB | ||||
53 | Futási hiba | 222ms | 521568 KiB | ||||
54 | Futási hiba | 172ms | 521576 KiB | ||||
55 | Futási hiba | 218ms | 521560 KiB | ||||
56 | Futási hiba | 218ms | 521564 KiB | ||||
57 | Futási hiba | 172ms | 521548 KiB | ||||
58 | Futási hiba | 217ms | 521564 KiB | ||||
59 | Futási hiba | 173ms | 521544 KiB | ||||
60 | Futási hiba | 170ms | 521516 KiB | ||||
61 | Futási hiba | 214ms | 521532 KiB | ||||
62 | Futási hiba | 216ms | 521536 KiB | ||||
63 | Futási hiba | 216ms | 521512 KiB | ||||
64 | Futási hiba | 168ms | 521520 KiB | ||||
65 | Futási hiba | 219ms | 521520 KiB | ||||
66 | Futási hiba | 209ms | 521524 KiB | ||||
67 | Futási hiba | 219ms | 521380 KiB | ||||
68 | Futási hiba | 219ms | 521384 KiB |