203272026-01-06 14:12:50hunzombiBináris Sakkcpp17Wrong answer 19/100423ms30412 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, 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;
    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({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;
    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
1Accepted1ms508 KiB
2Accepted1ms316 KiB
subtask20/11
3Accepted2ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Wrong answer1ms316 KiB
9Wrong answer1ms316 KiB
10Accepted2ms316 KiB
11Wrong answer2ms388 KiB
12Wrong answer2ms500 KiB
13Wrong answer2ms316 KiB
14Accepted1ms508 KiB
15Accepted1ms316 KiB
16Accepted1ms564 KiB
17Accepted2ms316 KiB
18Wrong answer1ms508 KiB
subtask30/19
19Accepted115ms12856 KiB
20Accepted26ms3252 KiB
21Accepted24ms3108 KiB
22Accepted307ms29364 KiB
23Accepted43ms5188 KiB
24Accepted13ms1844 KiB
25Accepted418ms30412 KiB
26Accepted423ms30408 KiB
27Accepted331ms30328 KiB
28Accepted351ms30328 KiB
29Accepted273ms29056 KiB
30Accepted247ms29564 KiB
31Wrong answer395ms30268 KiB
32Wrong answer356ms30328 KiB
subtask419/19
33Accepted2ms508 KiB
34Accepted2ms316 KiB
35Accepted1ms316 KiB
36Accepted1ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted2ms316 KiB
40Accepted1ms316 KiB
41Accepted2ms500 KiB
42Accepted2ms332 KiB
43Accepted1ms564 KiB
44Accepted1ms316 KiB
45Accepted2ms780 KiB
46Accepted2ms564 KiB
47Accepted2ms316 KiB
subtask50/51
48Accepted13ms1456 KiB
49Accepted32ms2692 KiB
50Accepted119ms9028 KiB
51Wrong answer143ms9604 KiB
52Wrong answer54ms3996 KiB
53Wrong answer75ms5428 KiB
54Wrong answer30ms2732 KiB
55Accepted12ms1332 KiB
56Accepted32ms2732 KiB
57Wrong answer171ms11200 KiB
58Wrong answer172ms11384 KiB
59Wrong answer172ms11476 KiB
60Wrong answer172ms11384 KiB
61Wrong answer174ms11464 KiB
62Wrong answer172ms11384 KiB
63Accepted125ms27000 KiB
64Accepted120ms27044 KiB
65Accepted134ms27004 KiB
66Accepted130ms27004 KiB
67Wrong answer173ms11384 KiB
68Wrong answer170ms11340 KiB