203242026-01-06 13:59:41chucknorrisBináris Sakkcpp17Hibás válasz 0/100405ms27512 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}); A2.push_back({c[i],i});A3.push_back({r[i] - c[i],i}); A4.push_back({r[i] + c[i],i});
    }

    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
2Hibás válasz4ms5100 KiB
subtask20/11
3Elfogadva4ms4916 KiB
4Hibás válasz6ms4916 KiB
5Hibás válasz4ms4916 KiB
6Hibás válasz4ms4916 KiB
7Elfogadva4ms4916 KiB
8Hibás válasz4ms5112 KiB
9Hibás válasz6ms5096 KiB
10Hibás válasz6ms5224 KiB
11Hibás válasz4ms4984 KiB
12Hibás válasz4ms5172 KiB
13Hibás válasz6ms5172 KiB
14Hibás válasz6ms5172 KiB
15Hibás válasz4ms5288 KiB
16Hibás válasz4ms5128 KiB
17Hibás válasz6ms5188 KiB
18Elfogadva6ms4920 KiB
subtask30/19
19Hibás válasz125ms14260 KiB
20Hibás válasz30ms7392 KiB
21Hibás válasz26ms7004 KiB
22Hibás válasz307ms26676 KiB
23Hibás válasz48ms8856 KiB
24Hibás válasz16ms6196 KiB
25Hibás válasz391ms27256 KiB
26Hibás válasz326ms27264 KiB
27Hibás válasz405ms27260 KiB
28Hibás válasz328ms27252 KiB
29Hibás válasz250ms27512 KiB
30Hibás válasz256ms27260 KiB
31Elfogadva347ms27256 KiB
32Elfogadva312ms27260 KiB
subtask40/19
33Elfogadva6ms5172 KiB
34Elfogadva6ms5172 KiB
35Elfogadva4ms4916 KiB
36Elfogadva6ms5100 KiB
37Elfogadva4ms4916 KiB
38Elfogadva6ms4916 KiB
39Elfogadva4ms4968 KiB
40Elfogadva6ms5172 KiB
41Elfogadva7ms5368 KiB
42Elfogadva4ms5164 KiB
43Hibás válasz4ms5172 KiB
44Hibás válasz6ms5172 KiB
45Hibás válasz4ms5172 KiB
46Hibás válasz6ms5136 KiB
47Elfogadva6ms5416 KiB
subtask50/51
48Elfogadva17ms6032 KiB
49Elfogadva37ms6856 KiB
50Elfogadva128ms11404 KiB
51Elfogadva150ms12228 KiB
52Elfogadva57ms7836 KiB
53Elfogadva79ms9096 KiB
54Elfogadva37ms6820 KiB
55Elfogadva14ms5956 KiB
56Elfogadva35ms6828 KiB
57Elfogadva180ms13688 KiB
58Elfogadva181ms13672 KiB
59Elfogadva182ms13696 KiB
60Elfogadva180ms13692 KiB
61Elfogadva184ms13684 KiB
62Elfogadva181ms13688 KiB
63Hibás válasz127ms23360 KiB
64Hibás válasz123ms23428 KiB
65Hibás válasz136ms23424 KiB
66Hibás válasz128ms23488 KiB
67Elfogadva180ms13688 KiB
68Elfogadva184ms13724 KiB