| 20325 | 2026-01-06 14:04:21 | chucknorris | Bináris Sakk | cpp17 | Elfogadva 100/100 | 393ms | 27512 KiB |
// NOTE: it is recommended to use this even if you don't understand the following code.
#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define MOD 1000000007
using namespace std;
vector<int>G[200002];
int vis[200002];
void dfs(int k){
vis[k] = 1;
for(auto i:G[k]) if(vis[i] == 0) dfs(i);
}
int main() {
// uncomment the two following lines if you want to read/write from files
// ifstream cin("input.txt");
// ofstream cout("output.txt");
ios::sync_with_stdio(false);
cin.tie(nullptr);
int R, C, N;
cin >> R >> C >> N;
vector<int> r(N), c(N);
for (int i = 0; i < N; ++i) {
cin >> r[i] >> c[i];
}
vector<pair<int, int>>A1, A2, A3, A4;
for(int i = 0; i < N; i++) {
A1.push_back({r[i], i+1}); A2.push_back({c[i],i+1});A3.push_back({r[i] - c[i],i+1}); A4.push_back({r[i] + c[i],i+1});
}
sort(A1.begin(), A1.end());
sort(A2.begin(), A2.end());
sort(A3.begin(), A3.end());
sort(A4.begin(), A4.end());
for(int i = 0; i < N - 1; i++){
if(A1[i].first == A1[i + 1].first) {
G[A1[i].second].push_back(A1[i+1].second); G[A1[i+1].second].push_back(A1[i].second);
}
if(A2[i].first == A2[i + 1].first) {
G[A2[i].second].push_back(A2[i+1].second); G[A2[i+1].second].push_back(A2[i].second);
}
if(A3[i].first == A3[i + 1].first) {
G[A3[i].second].push_back(A3[i+1].second); G[A3[i+1].second].push_back(A3[i].second);
}
if(A4[i].first == A4[i + 1].first) {
G[A4[i].second].push_back(A4[i+1].second); G[A4[i+1].second].push_back(A4[i].second);
}
}
long long ans = 1;
for(int i = 1; i <= N; i++){
if(vis[i] == 0){
ans = ans * 2 % MOD;
dfs(i);
}
}
cout << ans << endl; // print the result
return 0;
}
| Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Elfogadva | 4ms | 4916 KiB | ||||
| 2 | Elfogadva | 4ms | 4916 KiB | ||||
| subtask2 | 11/11 | ||||||
| 3 | Elfogadva | 6ms | 4916 KiB | ||||
| 4 | Elfogadva | 4ms | 4916 KiB | ||||
| 5 | Elfogadva | 4ms | 4916 KiB | ||||
| 6 | Elfogadva | 4ms | 4916 KiB | ||||
| 7 | Elfogadva | 4ms | 4928 KiB | ||||
| 8 | Elfogadva | 4ms | 4992 KiB | ||||
| 9 | Elfogadva | 6ms | 5152 KiB | ||||
| 10 | Elfogadva | 6ms | 5160 KiB | ||||
| 11 | Elfogadva | 7ms | 5364 KiB | ||||
| 12 | Elfogadva | 4ms | 5364 KiB | ||||
| 13 | Elfogadva | 6ms | 5016 KiB | ||||
| 14 | Elfogadva | 6ms | 5172 KiB | ||||
| 15 | Elfogadva | 6ms | 5212 KiB | ||||
| 16 | Elfogadva | 6ms | 5172 KiB | ||||
| 17 | Elfogadva | 4ms | 5172 KiB | ||||
| 18 | Elfogadva | 4ms | 4916 KiB | ||||
| subtask3 | 19/19 | ||||||
| 19 | Elfogadva | 109ms | 14328 KiB | ||||
| 20 | Elfogadva | 30ms | 7348 KiB | ||||
| 21 | Elfogadva | 27ms | 7020 KiB | ||||
| 22 | Elfogadva | 298ms | 26688 KiB | ||||
| 23 | Elfogadva | 46ms | 8836 KiB | ||||
| 24 | Elfogadva | 17ms | 6388 KiB | ||||
| 25 | Elfogadva | 389ms | 27256 KiB | ||||
| 26 | Elfogadva | 393ms | 27260 KiB | ||||
| 27 | Elfogadva | 314ms | 27244 KiB | ||||
| 28 | Elfogadva | 316ms | 27272 KiB | ||||
| 29 | Elfogadva | 238ms | 27512 KiB | ||||
| 30 | Elfogadva | 254ms | 27256 KiB | ||||
| 31 | Elfogadva | 358ms | 27252 KiB | ||||
| 32 | Elfogadva | 300ms | 27260 KiB | ||||
| subtask4 | 19/19 | ||||||
| 33 | Elfogadva | 7ms | 5172 KiB | ||||
| 34 | Elfogadva | 6ms | 5172 KiB | ||||
| 35 | Elfogadva | 4ms | 4916 KiB | ||||
| 36 | Elfogadva | 4ms | 5112 KiB | ||||
| 37 | Elfogadva | 4ms | 5000 KiB | ||||
| 38 | Elfogadva | 6ms | 4916 KiB | ||||
| 39 | Elfogadva | 6ms | 5128 KiB | ||||
| 40 | Elfogadva | 4ms | 5012 KiB | ||||
| 41 | Elfogadva | 6ms | 4944 KiB | ||||
| 42 | Elfogadva | 4ms | 5172 KiB | ||||
| 43 | Elfogadva | 6ms | 5172 KiB | ||||
| 44 | Elfogadva | 4ms | 5172 KiB | ||||
| 45 | Elfogadva | 6ms | 5016 KiB | ||||
| 46 | Elfogadva | 4ms | 5204 KiB | ||||
| 47 | Elfogadva | 6ms | 5172 KiB | ||||
| subtask5 | 51/51 | ||||||
| 48 | Elfogadva | 17ms | 5940 KiB | ||||
| 49 | Elfogadva | 34ms | 7080 KiB | ||||
| 50 | Elfogadva | 119ms | 11404 KiB | ||||
| 51 | Elfogadva | 136ms | 12148 KiB | ||||
| 52 | Elfogadva | 54ms | 7836 KiB | ||||
| 53 | Elfogadva | 72ms | 9100 KiB | ||||
| 54 | Elfogadva | 35ms | 6828 KiB | ||||
| 55 | Elfogadva | 16ms | 6004 KiB | ||||
| 56 | Elfogadva | 32ms | 6828 KiB | ||||
| 57 | Elfogadva | 163ms | 13664 KiB | ||||
| 58 | Elfogadva | 165ms | 13692 KiB | ||||
| 59 | Elfogadva | 166ms | 13692 KiB | ||||
| 60 | Elfogadva | 164ms | 13680 KiB | ||||
| 61 | Elfogadva | 168ms | 13688 KiB | ||||
| 62 | Elfogadva | 165ms | 13688 KiB | ||||
| 63 | Elfogadva | 116ms | 23420 KiB | ||||
| 64 | Elfogadva | 123ms | 23428 KiB | ||||
| 65 | Elfogadva | 128ms | 23500 KiB | ||||
| 66 | Elfogadva | 120ms | 23420 KiB | ||||
| 67 | Elfogadva | 163ms | 13692 KiB | ||||
| 68 | Elfogadva | 166ms | 13692 KiB | ||||