203302026-01-06 14:21:00hunzombiBináris Sakkcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms316 KiB
subtask211/11
3Elfogadva1ms316 KiB
4Elfogadva1ms508 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms508 KiB
7Elfogadva2ms500 KiB
8Elfogadva2ms316 KiB
9Elfogadva2ms316 KiB
10Elfogadva2ms316 KiB
11Elfogadva2ms316 KiB
12Elfogadva2ms316 KiB
13Elfogadva2ms316 KiB
14Elfogadva1ms564 KiB
15Elfogadva2ms316 KiB
16Elfogadva2ms756 KiB
17Elfogadva2ms316 KiB
18Elfogadva1ms316 KiB
subtask319/19
19Elfogadva116ms12712 KiB
20Elfogadva26ms3500 KiB
21Elfogadva24ms2856 KiB
22Elfogadva375ms29336 KiB
23Elfogadva43ms5468 KiB
24Elfogadva13ms2036 KiB
25Elfogadva412ms30076 KiB
26Elfogadva351ms30076 KiB
27Elfogadva354ms30160 KiB
28Elfogadva384ms30072 KiB
29Elfogadva257ms30364 KiB
30Elfogadva241ms30424 KiB
31Elfogadva395ms30300 KiB
32Elfogadva314ms30076 KiB
subtask419/19
33Elfogadva1ms512 KiB
34Elfogadva1ms512 KiB
35Elfogadva1ms332 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms320 KiB
38Elfogadva1ms460 KiB
39Elfogadva2ms316 KiB
40Elfogadva1ms316 KiB
41Elfogadva2ms316 KiB
42Elfogadva2ms316 KiB
43Elfogadva2ms316 KiB
44Elfogadva1ms564 KiB
45Elfogadva1ms316 KiB
46Elfogadva2ms564 KiB
47Elfogadva1ms316 KiB
subtask551/51
48Elfogadva12ms1568 KiB
49Elfogadva32ms2732 KiB
50Elfogadva115ms8844 KiB
51Elfogadva138ms9580 KiB
52Elfogadva52ms4064 KiB
53Elfogadva71ms5264 KiB
54Elfogadva30ms2732 KiB
55Elfogadva10ms1332 KiB
56Elfogadva29ms2568 KiB
57Elfogadva162ms11284 KiB
58Elfogadva168ms11460 KiB
59Elfogadva167ms11548 KiB
60Elfogadva166ms11424 KiB
61Elfogadva166ms11384 KiB
62Elfogadva168ms11352 KiB
63Elfogadva130ms26992 KiB
64Elfogadva126ms27004 KiB
65Elfogadva133ms27004 KiB
66Elfogadva128ms26996 KiB
67Elfogadva167ms11384 KiB
68Elfogadva168ms11464 KiB