203252026-01-06 14:04:21chucknorrisBináris Sakkcpp17Elfogadva 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;
}
RészfeladatÖsszpontTesztVerdiktIdőMemória
subtask10/0
1Elfogadva4ms4916 KiB
2Elfogadva4ms4916 KiB
subtask211/11
3Elfogadva6ms4916 KiB
4Elfogadva4ms4916 KiB
5Elfogadva4ms4916 KiB
6Elfogadva4ms4916 KiB
7Elfogadva4ms4928 KiB
8Elfogadva4ms4992 KiB
9Elfogadva6ms5152 KiB
10Elfogadva6ms5160 KiB
11Elfogadva7ms5364 KiB
12Elfogadva4ms5364 KiB
13Elfogadva6ms5016 KiB
14Elfogadva6ms5172 KiB
15Elfogadva6ms5212 KiB
16Elfogadva6ms5172 KiB
17Elfogadva4ms5172 KiB
18Elfogadva4ms4916 KiB
subtask319/19
19Elfogadva109ms14328 KiB
20Elfogadva30ms7348 KiB
21Elfogadva27ms7020 KiB
22Elfogadva298ms26688 KiB
23Elfogadva46ms8836 KiB
24Elfogadva17ms6388 KiB
25Elfogadva389ms27256 KiB
26Elfogadva393ms27260 KiB
27Elfogadva314ms27244 KiB
28Elfogadva316ms27272 KiB
29Elfogadva238ms27512 KiB
30Elfogadva254ms27256 KiB
31Elfogadva358ms27252 KiB
32Elfogadva300ms27260 KiB
subtask419/19
33Elfogadva7ms5172 KiB
34Elfogadva6ms5172 KiB
35Elfogadva4ms4916 KiB
36Elfogadva4ms5112 KiB
37Elfogadva4ms5000 KiB
38Elfogadva6ms4916 KiB
39Elfogadva6ms5128 KiB
40Elfogadva4ms5012 KiB
41Elfogadva6ms4944 KiB
42Elfogadva4ms5172 KiB
43Elfogadva6ms5172 KiB
44Elfogadva4ms5172 KiB
45Elfogadva6ms5016 KiB
46Elfogadva4ms5204 KiB
47Elfogadva6ms5172 KiB
subtask551/51
48Elfogadva17ms5940 KiB
49Elfogadva34ms7080 KiB
50Elfogadva119ms11404 KiB
51Elfogadva136ms12148 KiB
52Elfogadva54ms7836 KiB
53Elfogadva72ms9100 KiB
54Elfogadva35ms6828 KiB
55Elfogadva16ms6004 KiB
56Elfogadva32ms6828 KiB
57Elfogadva163ms13664 KiB
58Elfogadva165ms13692 KiB
59Elfogadva166ms13692 KiB
60Elfogadva164ms13680 KiB
61Elfogadva168ms13688 KiB
62Elfogadva165ms13688 KiB
63Elfogadva116ms23420 KiB
64Elfogadva123ms23428 KiB
65Elfogadva128ms23500 KiB
66Elfogadva120ms23420 KiB
67Elfogadva163ms13692 KiB
68Elfogadva166ms13692 KiB