203262026-01-06 14:06:22hunzombiBináris Sakkcpp17Wrong answer 19/100451ms30452 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;
    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({abs(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 = 0;
    vector<bool> sz(n, false);
    for (int i=0; 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
2Accepted1ms500 KiB
subtask20/11
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
10Accepted2ms316 KiB
11Wrong answer2ms316 KiB
12Wrong answer2ms332 KiB
13Wrong answer2ms396 KiB
14Accepted1ms564 KiB
15Accepted1ms316 KiB
16Accepted1ms316 KiB
17Accepted1ms316 KiB
18Wrong answer1ms316 KiB
subtask30/19
19Accepted134ms12848 KiB
20Accepted25ms3472 KiB
21Accepted24ms3076 KiB
22Accepted310ms29212 KiB
23Accepted41ms5276 KiB
24Accepted13ms1844 KiB
25Accepted451ms30356 KiB
26Accepted342ms30324 KiB
27Accepted441ms30392 KiB
28Accepted340ms30332 KiB
29Accepted241ms29048 KiB
30Accepted266ms29560 KiB
31Wrong answer365ms30452 KiB
32Wrong answer319ms30332 KiB
subtask419/19
33Accepted2ms316 KiB
34Accepted2ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted2ms316 KiB
39Accepted1ms316 KiB
40Accepted2ms508 KiB
41Accepted2ms316 KiB
42Accepted2ms316 KiB
43Accepted1ms316 KiB
44Accepted1ms748 KiB
45Accepted1ms392 KiB
46Accepted1ms564 KiB
47Accepted2ms316 KiB
subtask50/51
48Accepted13ms1580 KiB
49Accepted32ms2732 KiB
50Accepted119ms8900 KiB
51Wrong answer140ms9436 KiB
52Wrong answer52ms3996 KiB
53Wrong answer71ms5260 KiB
54Wrong answer30ms2700 KiB
55Accepted10ms1332 KiB
56Accepted30ms2636 KiB
57Wrong answer165ms11180 KiB
58Wrong answer170ms11388 KiB
59Wrong answer171ms11300 KiB
60Wrong answer171ms11524 KiB
61Wrong answer170ms11384 KiB
62Wrong answer168ms11544 KiB
63Accepted128ms26996 KiB
64Accepted128ms26992 KiB
65Accepted137ms27000 KiB
66Accepted134ms26876 KiB
67Wrong answer167ms11300 KiB
68Wrong answer168ms11388 KiB