203242026-01-06 13:59:41chucknorrisBináris Sakkcpp17Wrong answer 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;
}
SubtaskSumTestVerdictTimeMemory
subtask10/0
1Accepted4ms4916 KiB
2Wrong answer4ms5100 KiB
subtask20/11
3Accepted4ms4916 KiB
4Wrong answer6ms4916 KiB
5Wrong answer4ms4916 KiB
6Wrong answer4ms4916 KiB
7Accepted4ms4916 KiB
8Wrong answer4ms5112 KiB
9Wrong answer6ms5096 KiB
10Wrong answer6ms5224 KiB
11Wrong answer4ms4984 KiB
12Wrong answer4ms5172 KiB
13Wrong answer6ms5172 KiB
14Wrong answer6ms5172 KiB
15Wrong answer4ms5288 KiB
16Wrong answer4ms5128 KiB
17Wrong answer6ms5188 KiB
18Accepted6ms4920 KiB
subtask30/19
19Wrong answer125ms14260 KiB
20Wrong answer30ms7392 KiB
21Wrong answer26ms7004 KiB
22Wrong answer307ms26676 KiB
23Wrong answer48ms8856 KiB
24Wrong answer16ms6196 KiB
25Wrong answer391ms27256 KiB
26Wrong answer326ms27264 KiB
27Wrong answer405ms27260 KiB
28Wrong answer328ms27252 KiB
29Wrong answer250ms27512 KiB
30Wrong answer256ms27260 KiB
31Accepted347ms27256 KiB
32Accepted312ms27260 KiB
subtask40/19
33Accepted6ms5172 KiB
34Accepted6ms5172 KiB
35Accepted4ms4916 KiB
36Accepted6ms5100 KiB
37Accepted4ms4916 KiB
38Accepted6ms4916 KiB
39Accepted4ms4968 KiB
40Accepted6ms5172 KiB
41Accepted7ms5368 KiB
42Accepted4ms5164 KiB
43Wrong answer4ms5172 KiB
44Wrong answer6ms5172 KiB
45Wrong answer4ms5172 KiB
46Wrong answer6ms5136 KiB
47Accepted6ms5416 KiB
subtask50/51
48Accepted17ms6032 KiB
49Accepted37ms6856 KiB
50Accepted128ms11404 KiB
51Accepted150ms12228 KiB
52Accepted57ms7836 KiB
53Accepted79ms9096 KiB
54Accepted37ms6820 KiB
55Accepted14ms5956 KiB
56Accepted35ms6828 KiB
57Accepted180ms13688 KiB
58Accepted181ms13672 KiB
59Accepted182ms13696 KiB
60Accepted180ms13692 KiB
61Accepted184ms13684 KiB
62Accepted181ms13688 KiB
63Wrong answer127ms23360 KiB
64Wrong answer123ms23428 KiB
65Wrong answer136ms23424 KiB
66Wrong answer128ms23488 KiB
67Accepted180ms13688 KiB
68Accepted184ms13724 KiB