QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#704670#7900. Gifts from KnowledgehamsterWA 0ms3584kbC++232.3kb2024-11-02 20:35:132024-11-02 20:35:13

Judging History

你现在查看的是最新测评结果

  • [2024-11-02 20:35:13]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3584kb
  • [2024-11-02 20:35:13]
  • 提交

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'