203232026-01-06 13:59:02hunzombiBináris Sakkcpp17Hibás válasz 0/100217ms27008 KiB
#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1e9 + 7;

int r, c, n;
vector<pair<int, int>> nodes;
vector<vector<int>> graph;

void dfs1(int node, vector<bool>& sz) {
    sz[node] = true;
    for (int next : graph[node]) {
        if (!sz[next]) {
            dfs1(next, sz);
        }
    }
}

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

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

    cin >> r >> c >> n;
    vector<bool> visited(n + 1, false);
    graph.assign(n + 1, 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({abs(u - v), i}); v4.push_back({abs(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 || v2[i].first == v2[i + 1].first || v3[i].first == v3[i + 1].first || v4[i].first == v4[i + 1].first) {
            graph[i].push_back(i + 1);
            graph[i + 1].push_back(i);
        }
    }

    long long ans = 0;
    vector<bool> sz(n + 1, false);
    for (int i=1; i <= n; i++) {
        if (!sz[i]) {
            dfs1(i, sz);
            ans++;
        }
    }

    long long res = 1;

    while (ans > 0) {
        res = (res * 2) % MOD;
        ans--;
    }

    cout << res << '\n';

    return 0;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Hibás válasz1ms316 KiB
subtask20/11
3Elfogadva1ms316 KiB
4Hibás válasz1ms316 KiB
5Hibás válasz1ms316 KiB
6Hibás válasz1ms316 KiB
7Elfogadva1ms316 KiB
8Hibás válasz1ms316 KiB
9Hibás válasz1ms316 KiB
10Hibás válasz2ms316 KiB
11Hibás válasz2ms316 KiB
12Hibás válasz2ms512 KiB
13Hibás válasz2ms316 KiB
14Hibás válasz1ms316 KiB
15Hibás válasz1ms564 KiB
16Hibás válasz2ms564 KiB
17Hibás válasz1ms316 KiB
18Hibás válasz1ms316 KiB
subtask30/19
19Hibás válasz86ms11400 KiB
20Hibás válasz20ms2992 KiB
21Hibás válasz18ms2600 KiB
22Hibás válasz210ms26100 KiB
23Hibás válasz34ms4764 KiB
24Hibás válasz10ms1836 KiB
25Hibás válasz216ms26940 KiB
26Hibás válasz212ms27004 KiB
27Hibás válasz211ms26916 KiB
28Hibás válasz217ms27004 KiB
29Hibás válasz172ms27000 KiB
30Hibás válasz165ms27000 KiB
31Hibás válasz210ms26908 KiB
32Hibás válasz216ms27008 KiB
subtask40/19
33Elfogadva2ms316 KiB
34Elfogadva2ms316 KiB
35Elfogadva2ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms316 KiB
39Elfogadva1ms504 KiB
40Elfogadva1ms384 KiB
41Elfogadva2ms316 KiB
42Elfogadva2ms532 KiB
43Hibás válasz1ms316 KiB
44Hibás válasz1ms564 KiB
45Hibás válasz2ms580 KiB
46Hibás válasz2ms324 KiB
47Elfogadva1ms316 KiB
subtask50/51
48Elfogadva13ms1332 KiB
49Elfogadva34ms2760 KiB
50Elfogadva127ms8852 KiB
51Hibás válasz149ms9408 KiB
52Hibás válasz54ms3996 KiB
53Hibás válasz76ms5260 KiB
54Hibás válasz32ms2732 KiB
55Elfogadva12ms1336 KiB
56Elfogadva32ms2732 KiB
57Hibás válasz174ms11132 KiB
58Hibás válasz182ms11484 KiB
59Hibás válasz180ms11324 KiB
60Hibás válasz179ms11384 KiB
61Hibás válasz179ms11388 KiB
62Hibás válasz181ms11528 KiB
63Hibás válasz133ms27004 KiB
64Hibás válasz127ms27000 KiB
65Hibás válasz141ms27004 KiB
66Hibás válasz131ms26928 KiB
67Hibás válasz178ms11556 KiB
68Hibás válasz180ms11536 KiB