QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#277250#7894. Many Many HeadsSSH#RE 0ms0kbC++201.6kb2023-12-06 17:01:352023-12-06 17:01:35

Judging History

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

  • [2023-12-06 17:01:35]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-12-06 17:01:35]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
using namespace std;
void solve();
signed main(){
	cin.sync_with_stdio(0);
	cin.tie(0);
	int T = 1;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

#define mod 1000000007

void solve(){
	int n, m;
	cin >> n >> m;
	vector<int> cnt(m);
	vector<vector<int>> g(n, vector<int>(m));
	vector<vector<int>> pos(m);
	vector<vector<array<int,2>>> G(n + 10);
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			char x;
			cin >> x;
			g[i][j] = x - '0';
			if(g[i][j] == 1){
				cnt[j]++;
				pos[j].push_back(i);
			}
		}
	}
	
	for(int i = 0;i < m;i++){
		if(i != m - i - 1){
			if(cnt[i] + cnt[m - i - 1] > 2){
				cout << "0\n";
				return;
			}
		}
		else{
			if(cnt[i] > 1){
				cout << "0\n";
				return;
			}
		}
	}
	for(int i = 0;i < n;i++){
		for(int j = 0;j < m;j++){
			if(g[i][j] == 1){
				for(auto k:pos[j]){
					//dsu.merge(i + 1, k + 1);
					G[i + 1].push_back({k + 1, 0});
				}
				for(auto k:pos[m - j - 1]){
					//dsu.merge(i + 1, k + 1);
					if(k != i)G[i + 1].push_back({k + 1, 1});
				}
			}
		}
	}
	vector<int> vis(n + 10, -1);
	function<bool(int)> dfs = [&](int u){
		bool res = true;
		for(auto& [v, w]:G[u]){
			if(vis[v] != -1){
				if(vis[v] != (vis[u] ^ w)){
					return false;
				}
			}
			else{
				vis[v] = (vis[u] ^ w);
				res |= dfs(v);
			}
		}	
		return res;
	};
	int ans = 1;
	for(int i = 1;i <= n;i++){
		if(vis[i] == -1){
			vis[i] = 0;
			if(dfs(i)){
				ans *= 2;
				ans %= mod;
			}
			else{
				cout << "0\n";
				return;
			}
		}
	}
	cout << ans << "\n";
}

详细

Test #1:

score: 0
Runtime Error

input:

6
))
((()
[()]
()[()]()
([()])
([])([])

output:


result: