| 20325 | 2026-01-06 14:04:21 | chucknorris | Bináris Sakk | cpp17 | Accepted 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;
}
| Subtask | Sum | Test | Verdict | Time | Memory | ||
|---|---|---|---|---|---|---|---|
| subtask1 | 0/0 | ||||||
| 1 | Accepted | 4ms | 4916 KiB | ||||
| 2 | Accepted | 4ms | 4916 KiB | ||||
| subtask2 | 11/11 | ||||||
| 3 | Accepted | 6ms | 4916 KiB | ||||
| 4 | Accepted | 4ms | 4916 KiB | ||||
| 5 | Accepted | 4ms | 4916 KiB | ||||
| 6 | Accepted | 4ms | 4916 KiB | ||||
| 7 | Accepted | 4ms | 4928 KiB | ||||
| 8 | Accepted | 4ms | 4992 KiB | ||||
| 9 | Accepted | 6ms | 5152 KiB | ||||
| 10 | Accepted | 6ms | 5160 KiB | ||||
| 11 | Accepted | 7ms | 5364 KiB | ||||
| 12 | Accepted | 4ms | 5364 KiB | ||||
| 13 | Accepted | 6ms | 5016 KiB | ||||
| 14 | Accepted | 6ms | 5172 KiB | ||||
| 15 | Accepted | 6ms | 5212 KiB | ||||
| 16 | Accepted | 6ms | 5172 KiB | ||||
| 17 | Accepted | 4ms | 5172 KiB | ||||
| 18 | Accepted | 4ms | 4916 KiB | ||||
| subtask3 | 19/19 | ||||||
| 19 | Accepted | 109ms | 14328 KiB | ||||
| 20 | Accepted | 30ms | 7348 KiB | ||||
| 21 | Accepted | 27ms | 7020 KiB | ||||
| 22 | Accepted | 298ms | 26688 KiB | ||||
| 23 | Accepted | 46ms | 8836 KiB | ||||
| 24 | Accepted | 17ms | 6388 KiB | ||||
| 25 | Accepted | 389ms | 27256 KiB | ||||
| 26 | Accepted | 393ms | 27260 KiB | ||||
| 27 | Accepted | 314ms | 27244 KiB | ||||
| 28 | Accepted | 316ms | 27272 KiB | ||||
| 29 | Accepted | 238ms | 27512 KiB | ||||
| 30 | Accepted | 254ms | 27256 KiB | ||||
| 31 | Accepted | 358ms | 27252 KiB | ||||
| 32 | Accepted | 300ms | 27260 KiB | ||||
| subtask4 | 19/19 | ||||||
| 33 | Accepted | 7ms | 5172 KiB | ||||
| 34 | Accepted | 6ms | 5172 KiB | ||||
| 35 | Accepted | 4ms | 4916 KiB | ||||
| 36 | Accepted | 4ms | 5112 KiB | ||||
| 37 | Accepted | 4ms | 5000 KiB | ||||
| 38 | Accepted | 6ms | 4916 KiB | ||||
| 39 | Accepted | 6ms | 5128 KiB | ||||
| 40 | Accepted | 4ms | 5012 KiB | ||||
| 41 | Accepted | 6ms | 4944 KiB | ||||
| 42 | Accepted | 4ms | 5172 KiB | ||||
| 43 | Accepted | 6ms | 5172 KiB | ||||
| 44 | Accepted | 4ms | 5172 KiB | ||||
| 45 | Accepted | 6ms | 5016 KiB | ||||
| 46 | Accepted | 4ms | 5204 KiB | ||||
| 47 | Accepted | 6ms | 5172 KiB | ||||
| subtask5 | 51/51 | ||||||
| 48 | Accepted | 17ms | 5940 KiB | ||||
| 49 | Accepted | 34ms | 7080 KiB | ||||
| 50 | Accepted | 119ms | 11404 KiB | ||||
| 51 | Accepted | 136ms | 12148 KiB | ||||
| 52 | Accepted | 54ms | 7836 KiB | ||||
| 53 | Accepted | 72ms | 9100 KiB | ||||
| 54 | Accepted | 35ms | 6828 KiB | ||||
| 55 | Accepted | 16ms | 6004 KiB | ||||
| 56 | Accepted | 32ms | 6828 KiB | ||||
| 57 | Accepted | 163ms | 13664 KiB | ||||
| 58 | Accepted | 165ms | 13692 KiB | ||||
| 59 | Accepted | 166ms | 13692 KiB | ||||
| 60 | Accepted | 164ms | 13680 KiB | ||||
| 61 | Accepted | 168ms | 13688 KiB | ||||
| 62 | Accepted | 165ms | 13688 KiB | ||||
| 63 | Accepted | 116ms | 23420 KiB | ||||
| 64 | Accepted | 123ms | 23428 KiB | ||||
| 65 | Accepted | 128ms | 23500 KiB | ||||
| 66 | Accepted | 120ms | 23420 KiB | ||||
| 67 | Accepted | 163ms | 13692 KiB | ||||
| 68 | Accepted | 166ms | 13692 KiB | ||||