203282026-01-06 14:17:56hunzombiBináris Sakkcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask211/11
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
8Elfogadva2ms316 KiB
9Elfogadva1ms316 KiB
10Elfogadva2ms316 KiB
11Elfogadva2ms316 KiB
12Elfogadva2ms500 KiB
13Elfogadva2ms316 KiB
14Elfogadva1ms564 KiB
15Elfogadva1ms800 KiB
16Elfogadva2ms316 KiB
17Elfogadva1ms316 KiB
18Elfogadva1ms316 KiB
subtask319/19
19Elfogadva115ms12704 KiB
20Elfogadva26ms3504 KiB
21Elfogadva24ms2848 KiB
22Elfogadva367ms29440 KiB
23Elfogadva43ms5276 KiB
24Elfogadva12ms1820 KiB
25Elfogadva331ms30076 KiB
26Elfogadva400ms30328 KiB
27Elfogadva347ms30324 KiB
28Elfogadva388ms30072 KiB
29Elfogadva245ms30584 KiB
30Elfogadva284ms30324 KiB
31Elfogadva321ms30076 KiB
32Elfogadva316ms30076 KiB
subtask419/19
33Elfogadva1ms508 KiB
34Elfogadva1ms508 KiB
35Elfogadva1ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms508 KiB
38Elfogadva1ms316 KiB
39Elfogadva2ms316 KiB
40Elfogadva2ms316 KiB
41Elfogadva2ms316 KiB
42Elfogadva1ms316 KiB
43Elfogadva1ms316 KiB
44Elfogadva1ms564 KiB
45Elfogadva2ms380 KiB
46Elfogadva1ms316 KiB
47Elfogadva2ms316 KiB
subtask551/51
48Elfogadva13ms1568 KiB
49Elfogadva32ms2768 KiB
50Elfogadva118ms8952 KiB
51Elfogadva138ms9448 KiB
52Elfogadva52ms3940 KiB
53Elfogadva71ms5268 KiB
54Elfogadva30ms2732 KiB
55Elfogadva10ms1332 KiB
56Elfogadva30ms2680 KiB
57Elfogadva165ms11244 KiB
58Elfogadva170ms11528 KiB
59Elfogadva165ms11460 KiB
60Elfogadva165ms11384 KiB
61Elfogadva168ms11388 KiB
62Elfogadva168ms11384 KiB
63Elfogadva125ms26884 KiB
64Elfogadva126ms27000 KiB
65Elfogadva133ms27000 KiB
66Elfogadva134ms26928 KiB
67Elfogadva165ms11384 KiB
68Elfogadva168ms11428 KiB