9113 | 2024-02-14 17:04:27 | 111 | Bináris Sakk | cpp17 | Time limit exceeded 81/100 | 2.101s | 432628 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<set<int>> g(N * 2);
for (int i = 0; i < N; i++) {
g[i].insert(N + i);
g[N + i].insert(i);
}
for (auto m : {m1, m2}) {
for (auto [_, v] : m) {
sort(v.begin(), v.end());
for (int i = 0; i + 1 < v.size(); i++) {
g[v[i].second].insert(v[i + 1].second);
g[v[i + 1].second].insert(v[i].second);
}
}
}
for (auto m : {m3, m4}) {
for (auto [_, v] : m) {
sort(v.begin(), v.end());
for (int i = 0; i + 1 < v.size(); i++) {
g[N + v[i].second].insert(N + v[i + 1].second);
g[N + v[i + 1].second].insert(N + v[i].second);
}
}
}
vector<vector<int>> h;
scc(g, h);
cout << pow_mod(2, h.size()) << endl;
return 0;
}
Subtask | Sum | Test | Verdict | Time | Memory | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Accepted | 3ms | 1892 KiB | ||||
2 | Accepted | 3ms | 2136 KiB | ||||
subtask2 | 11/11 | ||||||
3 | Accepted | 3ms | 2308 KiB | ||||
4 | Accepted | 3ms | 2520 KiB | ||||
5 | Accepted | 3ms | 2744 KiB | ||||
6 | Accepted | 3ms | 2832 KiB | ||||
7 | Accepted | 3ms | 2948 KiB | ||||
8 | Accepted | 4ms | 4412 KiB | ||||
9 | Accepted | 4ms | 4672 KiB | ||||
10 | Accepted | 6ms | 4928 KiB | ||||
11 | Accepted | 6ms | 5220 KiB | ||||
12 | Accepted | 6ms | 5400 KiB | ||||
13 | Accepted | 7ms | 5292 KiB | ||||
14 | Accepted | 4ms | 5600 KiB | ||||
15 | Accepted | 6ms | 5652 KiB | ||||
16 | Accepted | 4ms | 5628 KiB | ||||
17 | Accepted | 4ms | 5604 KiB | ||||
18 | Accepted | 3ms | 4112 KiB | ||||
subtask3 | 0/19 | ||||||
19 | Accepted | 973ms | 178956 KiB | ||||
20 | Accepted | 126ms | 46800 KiB | ||||
21 | Accepted | 111ms | 42776 KiB | ||||
22 | Time limit exceeded | 2.078s | 207244 KiB | ||||
23 | Accepted | 233ms | 74776 KiB | ||||
24 | Accepted | 52ms | 25644 KiB | ||||
25 | Time limit exceeded | 2.069s | 213308 KiB | ||||
26 | Time limit exceeded | 2.085s | 214080 KiB | ||||
27 | Accepted | 1.973s | 424464 KiB | ||||
28 | Time limit exceeded | 2.101s | 214244 KiB | ||||
29 | Accepted | 1.106s | 410684 KiB | ||||
30 | Accepted | 1.09s | 410800 KiB | ||||
31 | Time limit exceeded | 2.089s | 214280 KiB | ||||
32 | Time limit exceeded | 2.076s | 215768 KiB | ||||
subtask4 | 19/19 | ||||||
33 | Accepted | 6ms | 6564 KiB | ||||
34 | Accepted | 6ms | 6692 KiB | ||||
35 | Accepted | 3ms | 5068 KiB | ||||
36 | Accepted | 3ms | 5604 KiB | ||||
37 | Accepted | 4ms | 5804 KiB | ||||
38 | Accepted | 4ms | 6120 KiB | ||||
39 | Accepted | 6ms | 7176 KiB | ||||
40 | Accepted | 6ms | 7176 KiB | ||||
41 | Accepted | 6ms | 7180 KiB | ||||
42 | Accepted | 7ms | 7120 KiB | ||||
43 | Accepted | 6ms | 7288 KiB | ||||
44 | Accepted | 6ms | 7312 KiB | ||||
45 | Accepted | 4ms | 7168 KiB | ||||
46 | Accepted | 6ms | 7232 KiB | ||||
47 | Accepted | 6ms | 7184 KiB | ||||
subtask5 | 51/51 | ||||||
48 | Accepted | 82ms | 35044 KiB | ||||
49 | Accepted | 270ms | 80940 KiB | ||||
50 | Accepted | 1.289s | 273032 KiB | ||||
51 | Accepted | 1.527s | 318660 KiB | ||||
52 | Accepted | 499ms | 129112 KiB | ||||
53 | Accepted | 731ms | 174788 KiB | ||||
54 | Accepted | 268ms | 78176 KiB | ||||
55 | Accepted | 64ms | 30732 KiB | ||||
56 | Accepted | 245ms | 76740 KiB | ||||
57 | Accepted | 1.907s | 378300 KiB | ||||
58 | Accepted | 1.93s | 395940 KiB | ||||
59 | Accepted | 1.521s | 395944 KiB | ||||
60 | Accepted | 1.947s | 396044 KiB | ||||
61 | Accepted | 1.922s | 386684 KiB | ||||
62 | Accepted | 1.529s | 386580 KiB | ||||
63 | Accepted | 1.021s | 432564 KiB | ||||
64 | Accepted | 1.052s | 432628 KiB | ||||
65 | Accepted | 1.023s | 380612 KiB | ||||
66 | Accepted | 870ms | 380540 KiB | ||||
67 | Accepted | 1.906s | 386788 KiB | ||||
68 | Accepted | 1.912s | 386588 KiB |