203252026-01-06 14:04:21chucknorrisBináris Sakkcpp17Accepted 100/100393ms27512 KiB
// NOTE: it is recommended to use this even if you don't understand the following code.

#include <fstream>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#define MOD 1000000007

using namespace std;

vector<int>G[200002];
int vis[200002];

void dfs(int k){
    vis[k] = 1;
    for(auto i:G[k]) if(vis[i] == 0) dfs(i);
}

int main() {
    // uncomment the two following lines if you want to read/write from files
    // ifstream cin("input.txt");
    // ofstream cout("output.txt");

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int R, C, N;
    cin >> R >> C >> N;

    vector<int> r(N), c(N);
    for (int i = 0; i < N; ++i) {
        cin >> r[i] >> c[i];
    }

    vector<pair<int, int>>A1, A2, A3, A4;

    for(int i = 0; i < N; i++) {
            A1.push_back({r[i], i+1}); A2.push_back({c[i],i+1});A3.push_back({r[i] - c[i],i+1}); A4.push_back({r[i] + c[i],i+1});
    }

    sort(A1.begin(), A1.end());
    sort(A2.begin(), A2.end());
    sort(A3.begin(), A3.end());
    sort(A4.begin(), A4.end());

    for(int i = 0; i < N - 1; i++){
        if(A1[i].first == A1[i + 1].first) {
                G[A1[i].second].push_back(A1[i+1].second); G[A1[i+1].second].push_back(A1[i].second);
        }
        if(A2[i].first == A2[i + 1].first) {
                G[A2[i].second].push_back(A2[i+1].second); G[A2[i+1].second].push_back(A2[i].second);
        }
        if(A3[i].first == A3[i + 1].first) {
                G[A3[i].second].push_back(A3[i+1].second); G[A3[i+1].second].push_back(A3[i].second);
        }
        if(A4[i].first == A4[i + 1].first) {
                G[A4[i].second].push_back(A4[i+1].second); G[A4[i+1].second].push_back(A4[i].second);
        }
    }



    long long ans = 1;
    for(int i = 1; i <= N; i++){
        if(vis[i] == 0){
            ans = ans * 2 % MOD;
            dfs(i);
        }
    }

    cout << ans << endl; // print the result

    return 0;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms4916 KiB
2Accepted4ms4916 KiB
subtask211/11
3Accepted6ms4916 KiB
4Accepted4ms4916 KiB
5Accepted4ms4916 KiB
6Accepted4ms4916 KiB
7Accepted4ms4928 KiB
8Accepted4ms4992 KiB
9Accepted6ms5152 KiB
10Accepted6ms5160 KiB
11Accepted7ms5364 KiB
12Accepted4ms5364 KiB
13Accepted6ms5016 KiB
14Accepted6ms5172 KiB
15Accepted6ms5212 KiB
16Accepted6ms5172 KiB
17Accepted4ms5172 KiB
18Accepted4ms4916 KiB
subtask319/19
19Accepted109ms14328 KiB
20Accepted30ms7348 KiB
21Accepted27ms7020 KiB
22Accepted298ms26688 KiB
23Accepted46ms8836 KiB
24Accepted17ms6388 KiB
25Accepted389ms27256 KiB
26Accepted393ms27260 KiB
27Accepted314ms27244 KiB
28Accepted316ms27272 KiB
29Accepted238ms27512 KiB
30Accepted254ms27256 KiB
31Accepted358ms27252 KiB
32Accepted300ms27260 KiB
subtask419/19
33Accepted7ms5172 KiB
34Accepted6ms5172 KiB
35Accepted4ms4916 KiB
36Accepted4ms5112 KiB
37Accepted4ms5000 KiB
38Accepted6ms4916 KiB
39Accepted6ms5128 KiB
40Accepted4ms5012 KiB
41Accepted6ms4944 KiB
42Accepted4ms5172 KiB
43Accepted6ms5172 KiB
44Accepted4ms5172 KiB
45Accepted6ms5016 KiB
46Accepted4ms5204 KiB
47Accepted6ms5172 KiB
subtask551/51
48Accepted17ms5940 KiB
49Accepted34ms7080 KiB
50Accepted119ms11404 KiB
51Accepted136ms12148 KiB
52Accepted54ms7836 KiB
53Accepted72ms9100 KiB
54Accepted35ms6828 KiB
55Accepted16ms6004 KiB
56Accepted32ms6828 KiB
57Accepted163ms13664 KiB
58Accepted165ms13692 KiB
59Accepted166ms13692 KiB
60Accepted164ms13680 KiB
61Accepted168ms13688 KiB
62Accepted165ms13688 KiB
63Accepted116ms23420 KiB
64Accepted123ms23428 KiB
65Accepted128ms23500 KiB
66Accepted120ms23420 KiB
67Accepted163ms13692 KiB
68Accepted166ms13692 KiB