QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704659 | #7900. Gifts from Knowledge | hamster | WA | 0ms | 3476kb | C++23 | 2.1kb | 2024-11-02 20:33:12 | 2024-11-02 20:33:15 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int MOD = 1e9 + 7;
vector<vector<int>> adj, adj_rev;
vector<int> ord, cmp;
vector<bool> vis;
int r, c;
void dfs1(int v) {
vis[v] = true;
for (int u : adj[v]) {
if (!vis[u]) dfs1(u);
}
ord.push_back(v);
}
void dfs2(int v, int cl) {
cmp[v] = cl;
for (int u : adj_rev[v]) {
if (cmp[u] == -1) dfs2(u, cl);
}
}
bool solve_2SAT(int vars) {
ord.clear();
vis.assign(vars * 2, false);
for (int i = 0; i < vars * 2; ++i) {
if (!vis[i]) dfs1(i);
}
cmp.assign(vars * 2, -1);
for (int i = 0, j = 0; i < vars * 2; ++i) {
int v = ord[vars * 2 - i - 1];
if (cmp[v] == -1) dfs2(v, j++);
}
for (int i = 0; i < vars; ++i) {
if (cmp[i * 2] == cmp[i * 2 + 1]) return false;
}
return true;
}
void add_clause(int x, bool xv, int y, bool yv) {
adj[x * 2 + !xv].push_back(y * 2 + yv);
adj[y * 2 + !yv].push_back(x * 2 + xv);
adj_rev[y * 2 + yv].push_back(x * 2 + !xv);
adj_rev[x * 2 + xv].push_back(y * 2 + !yv);
}
void Solve() {
cin >> r >> c;
vector<string> mat(r);
for (int i = 0; i < r; ++i) {
cin >> mat[i];
}
adj.assign(r * 2, vector<int>());
adj_rev.assign(r * 2, vector<int>());
for (int j = 0; j < c; ++j) {
int f = -1, s = -1;
for (int i = 0; i < r; ++i) {
if (mat[i][j] == '1') {
if (f == -1) f = i;
else if (s == -1) s = i;
else {
cout << 0 << "\n";
return;
}
}
}
if (f != -1 && s != -1) {
add_clause(f, false, s, false);
add_clause(f, true, s, true);
}
}
if (solve_2SAT(r)) {
int ways = 1;
for (int i = 0; i < r; ++i) {
ways = (ways * 2) % MOD;
}
cout << ways << "\n";
} else {
cout << 0 << "\n";
}
}
signed main() {
int T;
cin >> T;
while (T--) Solve();
}
详细
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3476kb
input:
3 3 5 01100 10001 00010 2 1 1 1 2 3 001 001
output:
8 4 4
result:
wrong answer 1st numbers differ - expected: '4', found: '8'