203262026-01-06 14:06:22hunzombiBináris Sakkcpp17Hibás válasz 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva1ms316 KiB
2Elfogadva1ms500 KiB
subtask20/11
3Elfogadva1ms316 KiB
4Elfogadva1ms316 KiB
5Elfogadva1ms316 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
8Hibás válasz1ms316 KiB
9Hibás válasz1ms316 KiB
10Elfogadva2ms316 KiB
11Hibás válasz2ms316 KiB
12Hibás válasz2ms332 KiB
13Hibás válasz2ms396 KiB
14Elfogadva1ms564 KiB
15Elfogadva1ms316 KiB
16Elfogadva1ms316 KiB
17Elfogadva1ms316 KiB
18Hibás válasz1ms316 KiB
subtask30/19
19Elfogadva134ms12848 KiB
20Elfogadva25ms3472 KiB
21Elfogadva24ms3076 KiB
22Elfogadva310ms29212 KiB
23Elfogadva41ms5276 KiB
24Elfogadva13ms1844 KiB
25Elfogadva451ms30356 KiB
26Elfogadva342ms30324 KiB
27Elfogadva441ms30392 KiB
28Elfogadva340ms30332 KiB
29Elfogadva241ms29048 KiB
30Elfogadva266ms29560 KiB
31Hibás válasz365ms30452 KiB
32Hibás válasz319ms30332 KiB
subtask419/19
33Elfogadva2ms316 KiB
34Elfogadva2ms316 KiB
35Elfogadva1ms316 KiB
36Elfogadva1ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva2ms316 KiB
39Elfogadva1ms316 KiB
40Elfogadva2ms508 KiB
41Elfogadva2ms316 KiB
42Elfogadva2ms316 KiB
43Elfogadva1ms316 KiB
44Elfogadva1ms748 KiB
45Elfogadva1ms392 KiB
46Elfogadva1ms564 KiB
47Elfogadva2ms316 KiB
subtask50/51
48Elfogadva13ms1580 KiB
49Elfogadva32ms2732 KiB
50Elfogadva119ms8900 KiB
51Hibás válasz140ms9436 KiB
52Hibás válasz52ms3996 KiB
53Hibás válasz71ms5260 KiB
54Hibás válasz30ms2700 KiB
55Elfogadva10ms1332 KiB
56Elfogadva30ms2636 KiB
57Hibás válasz165ms11180 KiB
58Hibás válasz170ms11388 KiB
59Hibás válasz171ms11300 KiB
60Hibás válasz171ms11524 KiB
61Hibás válasz170ms11384 KiB
62Hibás válasz168ms11544 KiB
63Elfogadva128ms26996 KiB
64Elfogadva128ms26992 KiB
65Elfogadva137ms27000 KiB
66Elfogadva134ms26876 KiB
67Hibás válasz167ms11300 KiB
68Hibás válasz168ms11388 KiB