QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#626361 | #7900. Gifts from Knowledge | ucup-team4906# | WA | 0ms | 3564kb | C++20 | 1.6kb | 2024-10-10 05:46:46 | 2024-10-10 05:46:46 |
Judging History
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'