9114 | 2024-02-14 17:07:18 | 111 | Bináris Sakk | cpp17 | Elfogadva 100/100 | 1.708s | 311588 KiB |
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define MOD 1000000007
int pow_mod(int x, int p, int m = MOD) {
int r = 1;
while (p > 0) {
if (p % 2 == 1) {
r *= x;
r %= m;
}
p /= 2;
x *= x;
x %= m;
}
return r;
}
void scc_dfs(const auto& g, auto& v, auto& s, int i) {
if (v[i]) {
return;
}
v[i] = true;
for (int j : g[i]) {
scc_dfs(g, v, s, j);
}
s.push_back(i);
}
void scc(const auto& g, auto& h) {
int N = g.size();
vector<int> v;
vector<int> s;
v.assign(N, false);
for (int i = 0; i < N; i++) {
scc_dfs(g, v, s, i);
}
vector<vector<int>> gt(N);
for (int i = 0; i < N; i++) {
for (int j : g[i]) {
gt[j].push_back(i);
}
}
reverse(s.begin(), s.end());
v.assign(N, false);
for (int i : s) {
if (v[i]) {
continue;
}
h.emplace_back();
scc_dfs(gt, v, h.back(), i);
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
#ifdef CB
freopen("in.txt", "r", stdin);
// freopen("out.txt", "w", stdout);
#endif
int R, C, N;
cin >> R >> C >> N;
map<int, vector<pii>> m1, m2, m3, m4;
for (int i = 0; i < N; i++) {
int r, c;
cin >> r >> c;
m1[r].emplace_back(r + c, i);
m2[c].emplace_back(r + c, i);
m3[r + c].emplace_back(r - c, i);
m4[r - c].emplace_back(r + c, i);
}
vector<vector<int>> g(N * 2);
for (int i = 0; i < N; i++) {
g[i].push_back(N + i);
g[N + i].push_back(i);
}
for (auto& [_, v] : m1) {
sort(v.begin(), v.end());
for (int i = 0; i + 1 < v.size(); i++) {
g[v[i].second].push_back(v[i + 1].second);
g[v[i + 1].second].push_back(v[i].second);
}
}
for (auto& [_, v] : m2) {
sort(v.begin(), v.end());
for (int i = 0; i + 1 < v.size(); i++) {
g[v[i].second].push_back(v[i + 1].second);
g[v[i + 1].second].push_back(v[i].second);
}
}
for (auto& [_, v] : m3) {
sort(v.begin(), v.end());
for (int i = 0; i + 1 < v.size(); i++) {
g[N + v[i].second].push_back(N + v[i + 1].second);
g[N + v[i + 1].second].push_back(N + v[i].second);
}
}
for (auto& [_, v] : m4) {
sort(v.begin(), v.end());
for (int i = 0; i + 1 < v.size(); i++) {
g[N + v[i].second].push_back(N + v[i + 1].second);
g[N + v[i + 1].second].push_back(N + v[i].second);
}
}
vector<vector<int>> h;
scc(g, h);
cout << pow_mod(2, h.size()) << endl;
return 0;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1892 KiB | ||||
2 | Elfogadva | 3ms | 2088 KiB | ||||
subtask2 | 11/11 | ||||||
3 | Elfogadva | 2ms | 2164 KiB | ||||
4 | Elfogadva | 3ms | 2300 KiB | ||||
5 | Elfogadva | 3ms | 2524 KiB | ||||
6 | Elfogadva | 3ms | 2720 KiB | ||||
7 | Elfogadva | 3ms | 2952 KiB | ||||
8 | Elfogadva | 4ms | 4036 KiB | ||||
9 | Elfogadva | 4ms | 4172 KiB | ||||
10 | Elfogadva | 4ms | 4464 KiB | ||||
11 | Elfogadva | 4ms | 4884 KiB | ||||
12 | Elfogadva | 4ms | 4992 KiB | ||||
13 | Elfogadva | 4ms | 5012 KiB | ||||
14 | Elfogadva | 4ms | 5160 KiB | ||||
15 | Elfogadva | 4ms | 5360 KiB | ||||
16 | Elfogadva | 4ms | 5260 KiB | ||||
17 | Elfogadva | 4ms | 5516 KiB | ||||
18 | Elfogadva | 3ms | 4176 KiB | ||||
subtask3 | 19/19 | ||||||
19 | Elfogadva | 518ms | 126808 KiB | ||||
20 | Elfogadva | 79ms | 34340 KiB | ||||
21 | Elfogadva | 71ms | 30644 KiB | ||||
22 | Elfogadva | 1.649s | 287856 KiB | ||||
23 | Elfogadva | 130ms | 53184 KiB | ||||
24 | Elfogadva | 37ms | 19192 KiB | ||||
25 | Elfogadva | 1.327s | 293908 KiB | ||||
26 | Elfogadva | 1.554s | 294212 KiB | ||||
27 | Elfogadva | 1.312s | 294252 KiB | ||||
28 | Elfogadva | 1.305s | 294192 KiB | ||||
29 | Elfogadva | 662ms | 286584 KiB | ||||
30 | Elfogadva | 625ms | 287884 KiB | ||||
31 | Elfogadva | 1.324s | 294452 KiB | ||||
32 | Elfogadva | 1.708s | 293336 KiB | ||||
subtask4 | 19/19 | ||||||
33 | Elfogadva | 4ms | 6108 KiB | ||||
34 | Elfogadva | 4ms | 6176 KiB | ||||
35 | Elfogadva | 3ms | 4876 KiB | ||||
36 | Elfogadva | 3ms | 5088 KiB | ||||
37 | Elfogadva | 3ms | 5180 KiB | ||||
38 | Elfogadva | 4ms | 5444 KiB | ||||
39 | Elfogadva | 4ms | 6368 KiB | ||||
40 | Elfogadva | 4ms | 6456 KiB | ||||
41 | Elfogadva | 4ms | 6452 KiB | ||||
42 | Elfogadva | 4ms | 6472 KiB | ||||
43 | Elfogadva | 4ms | 6480 KiB | ||||
44 | Elfogadva | 4ms | 6476 KiB | ||||
45 | Elfogadva | 4ms | 6564 KiB | ||||
46 | Elfogadva | 4ms | 6416 KiB | ||||
47 | Elfogadva | 4ms | 6556 KiB | ||||
subtask5 | 51/51 | ||||||
48 | Elfogadva | 57ms | 28372 KiB | ||||
49 | Elfogadva | 171ms | 65036 KiB | ||||
50 | Elfogadva | 939ms | 218780 KiB | ||||
51 | Elfogadva | 908ms | 252020 KiB | ||||
52 | Elfogadva | 312ms | 101488 KiB | ||||
53 | Elfogadva | 435ms | 137900 KiB | ||||
54 | Elfogadva | 158ms | 63044 KiB | ||||
55 | Elfogadva | 46ms | 25312 KiB | ||||
56 | Elfogadva | 157ms | 62052 KiB | ||||
57 | Elfogadva | 1.103s | 295996 KiB | ||||
58 | Elfogadva | 1.46s | 302320 KiB | ||||
59 | Elfogadva | 1.139s | 302292 KiB | ||||
60 | Elfogadva | 1.447s | 302296 KiB | ||||
61 | Elfogadva | 1.172s | 302432 KiB | ||||
62 | Elfogadva | 1.457s | 302292 KiB | ||||
63 | Elfogadva | 657ms | 311576 KiB | ||||
64 | Elfogadva | 569ms | 311588 KiB | ||||
65 | Elfogadva | 660ms | 298836 KiB | ||||
66 | Elfogadva | 652ms | 298984 KiB | ||||
67 | Elfogadva | 1.434s | 302460 KiB | ||||
68 | Elfogadva | 1.437s | 302460 KiB |