QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#626361#7900. Gifts from Knowledgeucup-team4906#WA 0ms3564kbC++201.6kb2024-10-10 05:46:462024-10-10 05:46:46

Judging History

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

  • [2024-10-10 05:46:46]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:3564kb
  • [2024-10-10 05:46:46]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef unsigned long long ull;

int n, m;

#define N 2000010
int fa[N];
int find(int x) {return (x == fa[x] ? x : fa[x] = find(fa[x]));}

void sol()
{
    cin >> n >> m;
    vector b(n + 1, vector<int>(m + 1, 0));
    for (int i = 1; i <= n; i ++)
    {
        string s;
        cin >> s;
        for (int j = 1; j <= m; j ++)
        {
            b[i][j] = s[j - 1] - '0';
        }
    }
    for (int i = 1; i <= 2 * n; i ++) fa[i] = i; 
    for (int j = 1; j <= m; j ++)
    {
        vector<int>vi;
        for (int i = 1; i <= n; i ++) if (b[i][j] == 1)vi.push_back(i);
        if (vi.size() > 2) {cout << "0\n"; return ;}
        for (int x : vi) for (int y : vi) if (x != y)
        {
            fa[find(x)] = find(y + n);
            fa[find(y)] = find(x + n);
        }
    }
    for (int j = 1; j <= m; j ++)
    {
        vector<int>vi, vt;
        for (int i = 1; i <= n; i ++)
        {
            if (b[i][j] == 1)vi.push_back(i);
            if (b[i][m - j + 1] == 1)vt.push_back(i);
        }
        for (int x : vi) for (int y : vt) if (x != y)
        {
            fa[find(x)] = find(y);
            fa[find(x + n)] = find(y + n);
        }
    }

    for (int i = 1; i <= n; i ++) if (find(i) == find(i + n)) {cout << "0\n"; return ;}
    int ans = 1; const int mod = int(1e9 + 7);
    for (int i = 1; i <= n; i ++) if (fa[i] == i) ans = (ans + ans) % mod;
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int T = 1;
    cin >> T;
    while (T --) sol();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 0ms
memory: 3564kb

input:

3
3 5
01100
10001
00010
2 1
1
1
2 3
001
001

output:

4
0
1

result:

wrong answer 3rd numbers differ - expected: '2', found: '1'