9113 | 2024-02-14 17:04:27 | 111 | Bináris Sakk | cpp17 | Időlimit túllépés 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;
}
Részfeladat | Összpont | Teszt | Verdikt | Idő | Memória | ||
---|---|---|---|---|---|---|---|
subtask1 | 0/0 | ||||||
1 | Elfogadva | 3ms | 1892 KiB | ||||
2 | Elfogadva | 3ms | 2136 KiB | ||||
subtask2 | 11/11 | ||||||
3 | Elfogadva | 3ms | 2308 KiB | ||||
4 | Elfogadva | 3ms | 2520 KiB | ||||
5 | Elfogadva | 3ms | 2744 KiB | ||||
6 | Elfogadva | 3ms | 2832 KiB | ||||
7 | Elfogadva | 3ms | 2948 KiB | ||||
8 | Elfogadva | 4ms | 4412 KiB | ||||
9 | Elfogadva | 4ms | 4672 KiB | ||||
10 | Elfogadva | 6ms | 4928 KiB | ||||
11 | Elfogadva | 6ms | 5220 KiB | ||||
12 | Elfogadva | 6ms | 5400 KiB | ||||
13 | Elfogadva | 7ms | 5292 KiB | ||||
14 | Elfogadva | 4ms | 5600 KiB | ||||
15 | Elfogadva | 6ms | 5652 KiB | ||||
16 | Elfogadva | 4ms | 5628 KiB | ||||
17 | Elfogadva | 4ms | 5604 KiB | ||||
18 | Elfogadva | 3ms | 4112 KiB | ||||
subtask3 | 0/19 | ||||||
19 | Elfogadva | 973ms | 178956 KiB | ||||
20 | Elfogadva | 126ms | 46800 KiB | ||||
21 | Elfogadva | 111ms | 42776 KiB | ||||
22 | Időlimit túllépés | 2.078s | 207244 KiB | ||||
23 | Elfogadva | 233ms | 74776 KiB | ||||
24 | Elfogadva | 52ms | 25644 KiB | ||||
25 | Időlimit túllépés | 2.069s | 213308 KiB | ||||
26 | Időlimit túllépés | 2.085s | 214080 KiB | ||||
27 | Elfogadva | 1.973s | 424464 KiB | ||||
28 | Időlimit túllépés | 2.101s | 214244 KiB | ||||
29 | Elfogadva | 1.106s | 410684 KiB | ||||
30 | Elfogadva | 1.09s | 410800 KiB | ||||
31 | Időlimit túllépés | 2.089s | 214280 KiB | ||||
32 | Időlimit túllépés | 2.076s | 215768 KiB | ||||
subtask4 | 19/19 | ||||||
33 | Elfogadva | 6ms | 6564 KiB | ||||
34 | Elfogadva | 6ms | 6692 KiB | ||||
35 | Elfogadva | 3ms | 5068 KiB | ||||
36 | Elfogadva | 3ms | 5604 KiB | ||||
37 | Elfogadva | 4ms | 5804 KiB | ||||
38 | Elfogadva | 4ms | 6120 KiB | ||||
39 | Elfogadva | 6ms | 7176 KiB | ||||
40 | Elfogadva | 6ms | 7176 KiB | ||||
41 | Elfogadva | 6ms | 7180 KiB | ||||
42 | Elfogadva | 7ms | 7120 KiB | ||||
43 | Elfogadva | 6ms | 7288 KiB | ||||
44 | Elfogadva | 6ms | 7312 KiB | ||||
45 | Elfogadva | 4ms | 7168 KiB | ||||
46 | Elfogadva | 6ms | 7232 KiB | ||||
47 | Elfogadva | 6ms | 7184 KiB | ||||
subtask5 | 51/51 | ||||||
48 | Elfogadva | 82ms | 35044 KiB | ||||
49 | Elfogadva | 270ms | 80940 KiB | ||||
50 | Elfogadva | 1.289s | 273032 KiB | ||||
51 | Elfogadva | 1.527s | 318660 KiB | ||||
52 | Elfogadva | 499ms | 129112 KiB | ||||
53 | Elfogadva | 731ms | 174788 KiB | ||||
54 | Elfogadva | 268ms | 78176 KiB | ||||
55 | Elfogadva | 64ms | 30732 KiB | ||||
56 | Elfogadva | 245ms | 76740 KiB | ||||
57 | Elfogadva | 1.907s | 378300 KiB | ||||
58 | Elfogadva | 1.93s | 395940 KiB | ||||
59 | Elfogadva | 1.521s | 395944 KiB | ||||
60 | Elfogadva | 1.947s | 396044 KiB | ||||
61 | Elfogadva | 1.922s | 386684 KiB | ||||
62 | Elfogadva | 1.529s | 386580 KiB | ||||
63 | Elfogadva | 1.021s | 432564 KiB | ||||
64 | Elfogadva | 1.052s | 432628 KiB | ||||
65 | Elfogadva | 1.023s | 380612 KiB | ||||
66 | Elfogadva | 870ms | 380540 KiB | ||||
67 | Elfogadva | 1.906s | 386788 KiB | ||||
68 | Elfogadva | 1.912s | 386588 KiB |