203232026-01-06 13:59:02hunzombiBináris Sakkcpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms316 KiB
2Wrong answer1ms316 KiB
subtask20/11
3Accepted1ms316 KiB
4Wrong answer1ms316 KiB
5Wrong answer1ms316 KiB
6Wrong answer1ms316 KiB
7Accepted1ms316 KiB
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
10Wrong answer2ms316 KiB
11Wrong answer2ms316 KiB
12Wrong answer2ms512 KiB
13Wrong answer2ms316 KiB
14Wrong answer1ms316 KiB
15Wrong answer1ms564 KiB
16Wrong answer2ms564 KiB
17Wrong answer1ms316 KiB
18Wrong answer1ms316 KiB
subtask30/19
19Wrong answer86ms11400 KiB
20Wrong answer20ms2992 KiB
21Wrong answer18ms2600 KiB
22Wrong answer210ms26100 KiB
23Wrong answer34ms4764 KiB
24Wrong answer10ms1836 KiB
25Wrong answer216ms26940 KiB
26Wrong answer212ms27004 KiB
27Wrong answer211ms26916 KiB
28Wrong answer217ms27004 KiB
29Wrong answer172ms27000 KiB
30Wrong answer165ms27000 KiB
31Wrong answer210ms26908 KiB
32Wrong answer216ms27008 KiB
subtask40/19
33Accepted2ms316 KiB
34Accepted2ms316 KiB
35Accepted2ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted1ms504 KiB
40Accepted1ms384 KiB
41Accepted2ms316 KiB
42Accepted2ms532 KiB
43Wrong answer1ms316 KiB
44Wrong answer1ms564 KiB
45Wrong answer2ms580 KiB
46Wrong answer2ms324 KiB
47Accepted1ms316 KiB
subtask50/51
48Accepted13ms1332 KiB
49Accepted34ms2760 KiB
50Accepted127ms8852 KiB
51Wrong answer149ms9408 KiB
52Wrong answer54ms3996 KiB
53Wrong answer76ms5260 KiB
54Wrong answer32ms2732 KiB
55Accepted12ms1336 KiB
56Accepted32ms2732 KiB
57Wrong answer174ms11132 KiB
58Wrong answer182ms11484 KiB
59Wrong answer180ms11324 KiB
60Wrong answer179ms11384 KiB
61Wrong answer179ms11388 KiB
62Wrong answer181ms11528 KiB
63Wrong answer133ms27004 KiB
64Wrong answer127ms27000 KiB
65Wrong answer141ms27004 KiB
66Wrong answer131ms26928 KiB
67Wrong answer178ms11556 KiB
68Wrong answer180ms11536 KiB