203302026-01-06 14:21:00hunzombiBináris Sakkcpp17Accepted 100/100412ms30424 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
4Accepted1ms508 KiB
5Accepted1ms316 KiB
6Accepted1ms508 KiB
7Accepted2ms500 KiB
8Accepted2ms316 KiB
9Accepted2ms316 KiB
10Accepted2ms316 KiB
11Accepted2ms316 KiB
12Accepted2ms316 KiB
13Accepted2ms316 KiB
14Accepted1ms564 KiB
15Accepted2ms316 KiB
16Accepted2ms756 KiB
17Accepted2ms316 KiB
18Accepted1ms316 KiB
subtask319/19
19Accepted116ms12712 KiB
20Accepted26ms3500 KiB
21Accepted24ms2856 KiB
22Accepted375ms29336 KiB
23Accepted43ms5468 KiB
24Accepted13ms2036 KiB
25Accepted412ms30076 KiB
26Accepted351ms30076 KiB
27Accepted354ms30160 KiB
28Accepted384ms30072 KiB
29Accepted257ms30364 KiB
30Accepted241ms30424 KiB
31Accepted395ms30300 KiB
32Accepted314ms30076 KiB
subtask419/19
33Accepted1ms512 KiB
34Accepted1ms512 KiB
35Accepted1ms332 KiB
36Accepted1ms316 KiB
37Accepted1ms320 KiB
38Accepted1ms460 KiB
39Accepted2ms316 KiB
40Accepted1ms316 KiB
41Accepted2ms316 KiB
42Accepted2ms316 KiB
43Accepted2ms316 KiB
44Accepted1ms564 KiB
45Accepted1ms316 KiB
46Accepted2ms564 KiB
47Accepted1ms316 KiB
subtask551/51
48Accepted12ms1568 KiB
49Accepted32ms2732 KiB
50Accepted115ms8844 KiB
51Accepted138ms9580 KiB
52Accepted52ms4064 KiB
53Accepted71ms5264 KiB
54Accepted30ms2732 KiB
55Accepted10ms1332 KiB
56Accepted29ms2568 KiB
57Accepted162ms11284 KiB
58Accepted168ms11460 KiB
59Accepted167ms11548 KiB
60Accepted166ms11424 KiB
61Accepted166ms11384 KiB
62Accepted168ms11352 KiB
63Accepted130ms26992 KiB
64Accepted126ms27004 KiB
65Accepted133ms27004 KiB
66Accepted128ms26996 KiB
67Accepted167ms11384 KiB
68Accepted168ms11464 KiB