203182026-01-06 13:13:25hunzombiBináris Sakkcpp17Hibás válasz 19/1002.101s6680 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);
        }
    }
}

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=1; i <= n; i++) {
        int u, v;
        cin >> u >> v;
        for (int j = 0; j < nodes.size(); j++) {
            if (visited[j + 1]) continue;
            visited[j + 1] = true;
            pair<int, int> node = nodes[j];
            int x = node.first, y = node.second;
            if (u == x || v == y || abs(x - y) == abs(u - v) || x + y == u + v) {
                graph[i].push_back(j + 1);
                graph[j + 1].push_back(i);
            }
        }
        nodes.push_back({u, v});
    }
    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
1Elfogadva1ms508 KiB
2Hibás válasz1ms316 KiB
subtask20/11
3Elfogadva1ms316 KiB
4Hibás válasz1ms508 KiB
5Elfogadva1ms508 KiB
6Elfogadva1ms316 KiB
7Elfogadva1ms316 KiB
8Hibás válasz1ms440 KiB
9Hibás válasz2ms316 KiB
10Hibás válasz2ms508 KiB
11Hibás válasz3ms316 KiB
12Hibás válasz3ms464 KiB
13Hibás válasz3ms508 KiB
14Elfogadva3ms316 KiB
15Elfogadva3ms484 KiB
16Elfogadva3ms500 KiB
17Elfogadva3ms316 KiB
18Elfogadva1ms508 KiB
subtask30/19
19Időlimit túllépés2.099s2980 KiB
20Hibás válasz717ms1208 KiB
21Hibás válasz551ms1048 KiB
22Időlimit túllépés2.099s5420 KiB
23Hibás válasz1.835s1736 KiB
24Hibás válasz178ms844 KiB
25Időlimit túllépés2.088s5640 KiB
26Időlimit túllépés2.072s5580 KiB
27Időlimit túllépés2.073s5564 KiB
28Időlimit túllépés2.086s5560 KiB
29Időlimit túllépés2.085s6680 KiB
30Időlimit túllépés2.086s6576 KiB
31Időlimit túllépés2.088s5696 KiB
32Időlimit túllépés2.079s5564 KiB
subtask419/19
33Elfogadva3ms316 KiB
34Elfogadva3ms500 KiB
35Elfogadva1ms316 KiB
36Elfogadva2ms316 KiB
37Elfogadva1ms316 KiB
38Elfogadva1ms316 KiB
39Elfogadva3ms316 KiB
40Elfogadva3ms316 KiB
41Elfogadva3ms316 KiB
42Elfogadva3ms316 KiB
43Elfogadva3ms316 KiB
44Elfogadva3ms316 KiB
45Elfogadva3ms472 KiB
46Elfogadva3ms476 KiB
47Elfogadva3ms316 KiB
subtask50/51
48Hibás válasz421ms860 KiB
49Időlimit túllépés2.099s1788 KiB
50Időlimit túllépés2.099s4304 KiB
51Időlimit túllépés2.101s4960 KiB
52Időlimit túllépés2.088s2480 KiB
53Időlimit túllépés2.079s2996 KiB
54Időlimit túllépés2.079s1776 KiB
55Hibás válasz314ms820 KiB
56Időlimit túllépés2.088s1932 KiB
57Időlimit túllépés2.086s5600 KiB
58Időlimit túllépés2.084s5556 KiB
59Időlimit túllépés2.084s5560 KiB
60Időlimit túllépés2.081s5552 KiB
61Időlimit túllépés2.076s5692 KiB
62Időlimit túllépés2.078s5636 KiB
63Időlimit túllépés2.078s6636 KiB
64Időlimit túllépés2.084s6596 KiB
65Időlimit túllépés2.085s6576 KiB
66Időlimit túllépés2.088s6576 KiB
67Időlimit túllépés2.088s5560 KiB
68Időlimit túllépés2.084s5612 KiB