| 20324 | 2026-01-06 13:59:41 | chucknorris | Bináris Sakk | cpp17 | Wrong answer 0/100 | 405ms | 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}); A2.push_back({c[i],i});A3.push_back({r[i] - c[i],i}); A4.push_back({r[i] + c[i],i});
}
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 | Wrong answer | 4ms | 5100 KiB | ||||
| subtask2 | 0/11 | ||||||
| 3 | Accepted | 4ms | 4916 KiB | ||||
| 4 | Wrong answer | 6ms | 4916 KiB | ||||
| 5 | Wrong answer | 4ms | 4916 KiB | ||||
| 6 | Wrong answer | 4ms | 4916 KiB | ||||
| 7 | Accepted | 4ms | 4916 KiB | ||||
| 8 | Wrong answer | 4ms | 5112 KiB | ||||
| 9 | Wrong answer | 6ms | 5096 KiB | ||||
| 10 | Wrong answer | 6ms | 5224 KiB | ||||
| 11 | Wrong answer | 4ms | 4984 KiB | ||||
| 12 | Wrong answer | 4ms | 5172 KiB | ||||
| 13 | Wrong answer | 6ms | 5172 KiB | ||||
| 14 | Wrong answer | 6ms | 5172 KiB | ||||
| 15 | Wrong answer | 4ms | 5288 KiB | ||||
| 16 | Wrong answer | 4ms | 5128 KiB | ||||
| 17 | Wrong answer | 6ms | 5188 KiB | ||||
| 18 | Accepted | 6ms | 4920 KiB | ||||
| subtask3 | 0/19 | ||||||
| 19 | Wrong answer | 125ms | 14260 KiB | ||||
| 20 | Wrong answer | 30ms | 7392 KiB | ||||
| 21 | Wrong answer | 26ms | 7004 KiB | ||||
| 22 | Wrong answer | 307ms | 26676 KiB | ||||
| 23 | Wrong answer | 48ms | 8856 KiB | ||||
| 24 | Wrong answer | 16ms | 6196 KiB | ||||
| 25 | Wrong answer | 391ms | 27256 KiB | ||||
| 26 | Wrong answer | 326ms | 27264 KiB | ||||
| 27 | Wrong answer | 405ms | 27260 KiB | ||||
| 28 | Wrong answer | 328ms | 27252 KiB | ||||
| 29 | Wrong answer | 250ms | 27512 KiB | ||||
| 30 | Wrong answer | 256ms | 27260 KiB | ||||
| 31 | Accepted | 347ms | 27256 KiB | ||||
| 32 | Accepted | 312ms | 27260 KiB | ||||
| subtask4 | 0/19 | ||||||
| 33 | Accepted | 6ms | 5172 KiB | ||||
| 34 | Accepted | 6ms | 5172 KiB | ||||
| 35 | Accepted | 4ms | 4916 KiB | ||||
| 36 | Accepted | 6ms | 5100 KiB | ||||
| 37 | Accepted | 4ms | 4916 KiB | ||||
| 38 | Accepted | 6ms | 4916 KiB | ||||
| 39 | Accepted | 4ms | 4968 KiB | ||||
| 40 | Accepted | 6ms | 5172 KiB | ||||
| 41 | Accepted | 7ms | 5368 KiB | ||||
| 42 | Accepted | 4ms | 5164 KiB | ||||
| 43 | Wrong answer | 4ms | 5172 KiB | ||||
| 44 | Wrong answer | 6ms | 5172 KiB | ||||
| 45 | Wrong answer | 4ms | 5172 KiB | ||||
| 46 | Wrong answer | 6ms | 5136 KiB | ||||
| 47 | Accepted | 6ms | 5416 KiB | ||||
| subtask5 | 0/51 | ||||||
| 48 | Accepted | 17ms | 6032 KiB | ||||
| 49 | Accepted | 37ms | 6856 KiB | ||||
| 50 | Accepted | 128ms | 11404 KiB | ||||
| 51 | Accepted | 150ms | 12228 KiB | ||||
| 52 | Accepted | 57ms | 7836 KiB | ||||
| 53 | Accepted | 79ms | 9096 KiB | ||||
| 54 | Accepted | 37ms | 6820 KiB | ||||
| 55 | Accepted | 14ms | 5956 KiB | ||||
| 56 | Accepted | 35ms | 6828 KiB | ||||
| 57 | Accepted | 180ms | 13688 KiB | ||||
| 58 | Accepted | 181ms | 13672 KiB | ||||
| 59 | Accepted | 182ms | 13696 KiB | ||||
| 60 | Accepted | 180ms | 13692 KiB | ||||
| 61 | Accepted | 184ms | 13684 KiB | ||||
| 62 | Accepted | 181ms | 13688 KiB | ||||
| 63 | Wrong answer | 127ms | 23360 KiB | ||||
| 64 | Wrong answer | 123ms | 23428 KiB | ||||
| 65 | Wrong answer | 136ms | 23424 KiB | ||||
| 66 | Wrong answer | 128ms | 23488 KiB | ||||
| 67 | Accepted | 180ms | 13688 KiB | ||||
| 68 | Accepted | 184ms | 13724 KiB | ||||