QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#704659#7900. Gifts from KnowledgehamsterWA 0ms3476kbC++232.1kb2024-11-02 20:33:122024-11-02 20:33:15

Judging History

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

  • [2024-11-02 20:33:15]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3476kb
  • [2024-11-02 20:33:12]
  • 提交

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();
}

Details

Tip: Click on the bar to expand more detailed information

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'