QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#572123#7900. Gifts from KnowledgeyanshanjiahongWA 33ms35504kbC++201.7kb2024-09-18 12:11:552024-09-18 12:11:56

Judging History

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

  • [2024-09-18 12:11:56]
  • 评测
  • 测评结果:WA
  • 用时:33ms
  • 内存:35504kb
  • [2024-09-18 12:11:55]
  • 提交

answer

#include<bits/stdc++.h>
#include<bits/extc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define mp make_pair
#define sec second
#define fir first
#define pii pair<int,int>
#define lowbit(i) i&-i
#define int long long
using namespace std;
typedef long long ll;
const int N=1e6+5,M=1e6+5,S=(1<<15)+5,inf=(ll)1e18+7,mo=1e9+7;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
int T;
int n,m;
string s[N];
vector<int>h[N],fh[N];
struct bcj{
    int fa[N];
    void init(){
        rep(i,1,2*n)
            fa[i]=i;
    }
    int find(int x){
        if(fa[x]==x)return x;
        return fa[x]=find(fa[x]);
    }
    void merge(int x,int y){
        x=find(x),y=find(y);
        if(x==y)return;
        fa[x]=y;
    }
}B;
void solve(){
    read(n),read(m);
    B.init();
    rep(i,0,m-1)
        h[i].clear(),fh[i].clear();
    rep(i,1,n){
        cin>>s[i];
        rep(j,0,m-1){
            int fj=m-1-j;
            if(s[i][j]=='0')continue;
            if(!h[j].empty())B.merge(h[j].back()+n,i),B.merge(h[j].back(),i+n);
            h[j].push_back(i);
            if(!fh[j].empty())B.merge(fh[j].back(),i),B.merge(fh[j].back()+n,i+n);
            fh[fj].push_back(i);
        }
    }
    int ans=1;
    rep(i,1,n){
        if(B.find(i)==B.find(i+n)){
            puts("0");
            return;
        }
        if(B.find(i)==i)ans*=2,ans%=mo;
    }
    printf("%lld\n",ans);
}
signed main(){
    read(T);
    while(T--)
        solve();
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 35368kb

input:

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

output:

4
0
2

result:

ok 3 number(s): "4 0 2"

Test #2:

score: 0
Accepted
time: 32ms
memory: 35284kb

input:

15613
10 10
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
0000000000
15 8
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
00000000
1 5
00000
5 9
000000000
000000000
0000...

output:

1024
32768
2
32
32768
128
32
16
16
2
16384
16384
128
128
32768
8192
128
64
16384
2
4
2
4096
16
4096
1024
32768
32768
16384
8
128
2
16
4096
8192
32768
8192
8192
16
16384
16384
256
128
8
256
8
4096
512
2
4
32
32
2
64
512
1024
32768
32768
2
64
16384
16
8192
16
256
16
64
8192
8192
64
1024
2
32768
2
4
51...

result:

ok 15613 numbers

Test #3:

score: -100
Wrong Answer
time: 33ms
memory: 35504kb

input:

15759
9 6
000000
000000
000000
000000
000000
000000
000000
000000
000000
5 15
010000000000000
000000000000000
000000000000000
000100000000000
000100000000000
14 12
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000000000
000000...

output:

512
16
16384
512
1024
4096
32768
4
2
512
512
512
512
8
2
256
16
4096
512
64
16
4096
512
32
32768
8192
32
2048
128
16
4096
64
32768
256
32
16384
8
512
32
2048
8
16
1024
2048
128
64
32
8
512
8
8192
256
8192
32768
2
8
512
512
256
32
2
2048
8192
8
64
8
2
16384
32768
32768
1024
4096
16384
16384
128
256
4...

result:

wrong answer 695th numbers differ - expected: '0', found: '128'