203182026-01-06 13:13:25hunzombiBináris Sakkcpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted1ms508 KiB
2Wrong answer1ms316 KiB
subtask20/11
3Accepted1ms316 KiB
4Wrong answer1ms508 KiB
5Accepted1ms508 KiB
6Accepted1ms316 KiB
7Accepted1ms316 KiB
8Wrong answer1ms440 KiB
9Wrong answer2ms316 KiB
10Wrong answer2ms508 KiB
11Wrong answer3ms316 KiB
12Wrong answer3ms464 KiB
13Wrong answer3ms508 KiB
14Accepted3ms316 KiB
15Accepted3ms484 KiB
16Accepted3ms500 KiB
17Accepted3ms316 KiB
18Accepted1ms508 KiB
subtask30/19
19Time limit exceeded2.099s2980 KiB
20Wrong answer717ms1208 KiB
21Wrong answer551ms1048 KiB
22Time limit exceeded2.099s5420 KiB
23Wrong answer1.835s1736 KiB
24Wrong answer178ms844 KiB
25Time limit exceeded2.088s5640 KiB
26Time limit exceeded2.072s5580 KiB
27Time limit exceeded2.073s5564 KiB
28Time limit exceeded2.086s5560 KiB
29Time limit exceeded2.085s6680 KiB
30Time limit exceeded2.086s6576 KiB
31Time limit exceeded2.088s5696 KiB
32Time limit exceeded2.079s5564 KiB
subtask419/19
33Accepted3ms316 KiB
34Accepted3ms500 KiB
35Accepted1ms316 KiB
36Accepted2ms316 KiB
37Accepted1ms316 KiB
38Accepted1ms316 KiB
39Accepted3ms316 KiB
40Accepted3ms316 KiB
41Accepted3ms316 KiB
42Accepted3ms316 KiB
43Accepted3ms316 KiB
44Accepted3ms316 KiB
45Accepted3ms472 KiB
46Accepted3ms476 KiB
47Accepted3ms316 KiB
subtask50/51
48Wrong answer421ms860 KiB
49Time limit exceeded2.099s1788 KiB
50Time limit exceeded2.099s4304 KiB
51Time limit exceeded2.101s4960 KiB
52Time limit exceeded2.088s2480 KiB
53Time limit exceeded2.079s2996 KiB
54Time limit exceeded2.079s1776 KiB
55Wrong answer314ms820 KiB
56Time limit exceeded2.088s1932 KiB
57Time limit exceeded2.086s5600 KiB
58Time limit exceeded2.084s5556 KiB
59Time limit exceeded2.084s5560 KiB
60Time limit exceeded2.081s5552 KiB
61Time limit exceeded2.076s5692 KiB
62Time limit exceeded2.078s5636 KiB
63Time limit exceeded2.078s6636 KiB
64Time limit exceeded2.084s6596 KiB
65Time limit exceeded2.085s6576 KiB
66Time limit exceeded2.088s6576 KiB
67Time limit exceeded2.088s5560 KiB
68Time limit exceeded2.084s5612 KiB