203282026-01-06 14:17:56hunzombiBináris Sakkcpp17Accepted 100/100400ms30584 KiB
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int r, c, n;
vector<vector<int>> graph;
vector<bool> sz;

void dfs1(int node) {
    sz[node] = true;
    for (int next : graph[node]) {
        if (!sz[next]) {
            dfs1(next);
        }
    }
}

vector<pair<int, int>> v1, v2, v3, v4;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> r >> c >> n;
    sz.assign(n, false);
    graph.assign(n, vector<int>(0));
    for (int i=0; i < n; i++) {
        int u, v;
        cin >> u >> v;
        v1.push_back({u, i}); v2.push_back({v, i}); v3.push_back({u - v, i}); v4.push_back({u + v, i});
    }

    sort(v1.begin(), v1.end());
    sort(v2.begin(), v2.end());
    sort(v3.begin(), v3.end());
    sort(v4.begin(), v4.end());

    for (int i=0; i < n - 1; i++) {
        if (v1[i].first == v1[i + 1].first) {
            graph[v1[i].second].push_back(v1[i + 1].second);
            graph[v1[i + 1].second].push_back(v1[i].second);
        }
        if (v2[i].first == v2[i + 1].first) {
            graph[v2[i].second].push_back(v2[i + 1].second);
            graph[v2[i + 1].second].push_back(v2[i].second);
        }
        if (v3[i].first == v3[i + 1].first) {
            graph[v3[i].second].push_back(v3[i + 1].second);
            graph[v3[i + 1].second].push_back(v3[i].second);
        }
        if (v4[i].first == v4[i + 1].first) {
            graph[v4[i].second].push_back(v4[i + 1].second);
            graph[v4[i + 1].second].push_back(v4[i].second);
        }
    }

    long long ans = 1;
    for (int i=0; i < n; i++) {
        if (!sz[i]) {
            dfs1(i);
            ans = (ans * 2) % MOD;
        }
    }

    cout << ans << '\n';

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask211/11
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Accepted2ms316 KiB
9Accepted1ms316 KiB
10Accepted2ms316 KiB
11Accepted2ms316 KiB
12Accepted2ms500 KiB
13Accepted2ms316 KiB
14Accepted1ms564 KiB
15Accepted1ms800 KiB
16Accepted2ms316 KiB
17Accepted1ms316 KiB
18Accepted1ms316 KiB
subtask319/19
19Accepted115ms12704 KiB
20Accepted26ms3504 KiB
21Accepted24ms2848 KiB
22Accepted367ms29440 KiB
23Accepted43ms5276 KiB
24Accepted12ms1820 KiB
25Accepted331ms30076 KiB
26Accepted400ms30328 KiB
27Accepted347ms30324 KiB
28Accepted388ms30072 KiB
29Accepted245ms30584 KiB
30Accepted284ms30324 KiB
31Accepted321ms30076 KiB
32Accepted316ms30076 KiB
subtask419/19
33Accepted1ms508 KiB
34Accepted1ms508 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms508 KiB
38Accepted1ms316 KiB
39Accepted2ms316 KiB
40Accepted2ms316 KiB
41Accepted2ms316 KiB
42Accepted1ms316 KiB
43Accepted1ms316 KiB
44Accepted1ms564 KiB
45Accepted2ms380 KiB
46Accepted1ms316 KiB
47Accepted2ms316 KiB
subtask551/51
48Accepted13ms1568 KiB
49Accepted32ms2768 KiB
50Accepted118ms8952 KiB
51Accepted138ms9448 KiB
52Accepted52ms3940 KiB
53Accepted71ms5268 KiB
54Accepted30ms2732 KiB
55Accepted10ms1332 KiB
56Accepted30ms2680 KiB
57Accepted165ms11244 KiB
58Accepted170ms11528 KiB
59Accepted165ms11460 KiB
60Accepted165ms11384 KiB
61Accepted168ms11388 KiB
62Accepted168ms11384 KiB
63Accepted125ms26884 KiB
64Accepted126ms27000 KiB
65Accepted133ms27000 KiB
66Accepted134ms26928 KiB
67Accepted165ms11384 KiB
68Accepted168ms11428 KiB