203172026-01-06 12:57:10hunzombiBináris Sakkcpp17Wrong answer 19/1002.101s262144 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;
    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++) {
            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
1Accepted1ms316 KiB
2Accepted1ms316 KiB
subtask20/11
3Accepted1ms316 KiB
4Accepted1ms316 KiB
5Accepted1ms316 KiB
6Accepted1ms316 KiB
7Accepted1ms388 KiB
8Wrong answer2ms508 KiB
9Wrong answer2ms316 KiB
10Accepted3ms564 KiB
11Wrong answer4ms484 KiB
12Wrong answer4ms316 KiB
13Wrong answer4ms316 KiB
14Accepted13ms4308 KiB
15Accepted12ms4404 KiB
16Accepted12ms4308 KiB
17Accepted13ms4384 KiB
18Wrong answer1ms508 KiB
subtask30/19
19Time limit exceeded2.091s60280 KiB
20Accepted1.261s89264 KiB
21Accepted838ms12464 KiB
22Time limit exceeded2.088s35452 KiB
23Time limit exceeded2.086s93872 KiB
24Accepted319ms22836 KiB
25Time limit exceeded2.079s24240 KiB
26Time limit exceeded2.092s24480 KiB
27Time limit exceeded2.096s24496 KiB
28Time limit exceeded2.089s24516 KiB
29Time limit exceeded2.096s224944 KiB
30Time limit exceeded2.101s223408 KiB
31Time limit exceeded2.088s24496 KiB
32Time limit exceeded2.078s26032 KiB
subtask419/19
33Accepted3ms316 KiB
34Accepted4ms316 KiB
35Accepted1ms512 KiB
36Accepted2ms316 KiB
37Accepted1ms428 KiB
38Accepted1ms316 KiB
39Accepted4ms332 KiB
40Accepted4ms316 KiB
41Accepted4ms316 KiB
42Accepted4ms500 KiB
43Accepted12ms4404 KiB
44Accepted12ms4556 KiB
45Accepted13ms4416 KiB
46Accepted12ms4560 KiB
47Accepted4ms456 KiB
subtask50/51
48Accepted601ms912 KiB
49Time limit exceeded2.099s1724 KiB
50Time limit exceeded2.099s4024 KiB
51Time limit exceeded2.098s4584 KiB
52Time limit exceeded2.075s2276 KiB
53Time limit exceeded2.073s2868 KiB
54Time limit exceeded2.073s1716 KiB
55Accepted448ms1052 KiB
56Time limit exceeded2.081s1672 KiB
57Time limit exceeded2.088s5288 KiB
58Time limit exceeded2.091s5484 KiB
59Time limit exceeded2.091s5428 KiB
60Time limit exceeded2.086s5568 KiB
61Time limit exceeded2.075s5380 KiB
62Time limit exceeded2.081s5444 KiB
63Runtime error670ms262144 KiB
64Runtime error669ms262144 KiB
65Runtime error771ms262144 KiB
66Runtime error657ms262144 KiB
67Time limit exceeded2.085s5428 KiB
68Time limit exceeded2.081s5476 KiB