QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#704670 | #7900. Gifts from Knowledge | hamster | WA | 0ms | 3584kb | C++23 | 2.3kb | 2024-11-02 20:35:13 | 2024-11-02 20:35:13 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
const int MOD = 1e9 + 7;
vector<vector<int>> adj, adj_rev;
vector<int> order, component;
vector<bool> visited;
int n, m;
void dfs1(int v) {
visited[v] = true;
for (int u : adj[v])
if (!visited[u])
dfs1(u);
order.push_back(v);
}
void dfs2(int v, int cl) {
component[v] = cl;
for (int u : adj_rev[v])
if (component[u] == -1)
dfs2(u, cl);
}
int solve_2sat(int vars) {
visited.assign(vars * 2, false);
for (int i = 0; i < vars * 2; ++i)
if (!visited[i])
dfs1(i);
component.assign(vars * 2, -1);
for (int i = 0, j = 0; i < vars * 2; ++i) {
int v = order[vars * 2 - i - 1];
if (component[v] == -1)
dfs2(v, j++);
}
for (int i = 0; i < vars; ++i)
if (component[i] == component[i + vars])
return 0;
vector<int> comp_count(vars * 2, 0);
for (int i = 0; i < vars * 2; ++i)
comp_count[component[i]]++;
int cnt = 0;
for (int i = 0; i < vars * 2; ++i)
if (comp_count[i] > 0)
cnt++;
return (1LL << (cnt / 2)) % MOD;
}
void Solve() {
cin >> n >> m;
vector<string> matrix(n);
for (int i = 0; i < n; ++i)
cin >> matrix[i];
adj.assign(n * 2, vector<int>());
adj_rev.assign(n * 2, vector<int>());
for (int j = 0; j < m; ++j) {
vector<int> ones;
for (int i = 0; i < n; ++i) {
if (matrix[i][j] == '1')
ones.push_back(i);
}
if (ones.size() > 2) {
cout << 0 << "\n";
return;
}
if (ones.size() == 2) {
int u = ones[0], v = ones[1];
adj[u].push_back(v + n);
adj[v].push_back(u + n);
adj[u + n].push_back(v);
adj[v + n].push_back(u);
adj_rev[v + n].push_back(u);
adj_rev[u + n].push_back(v);
adj_rev[v].push_back(u + n);
adj_rev[u].push_back(v + n);
}
}
cout << solve_2sat(n) << "\n";
}
signed main() {
int Task;
cin >> Task;
while (Task--) Solve();
}
詳細信息
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 3584kb
input:
3 3 5 01100 10001 00010 2 1 1 1 2 3 001 001
output:
8 2 2
result:
wrong answer 1st numbers differ - expected: '4', found: '8'