This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
struct DSU{
vector<vector<array<int,2>>> par;
vector<vector<int>> sz;
DSU(int n, int m){
par.resize(n,vector<array<int,2>>(m));
sz.resize(n,vector<int>(m,1));
for (int i = 0; i < n; ++i)
{
for (int j = 0; j < m; ++j){
par[i][j]={i,j};
}
}
}
array<int,2> find(array<int,2> node){
if (par[node[0]][node[1]]==node) return node;
return par[node[0]][node[1]]=find(par[node[0]][node[1]]);
}
void merge(array<int,2> a, array<int,2> b){
a=find(a);
b=find(b);
if (a==b) return;
sz[a[0]][a[1]]+=sz[b[0]][b[1]];
sz[b[0]][b[1]]=0;
par[b[0]][b[1]]=a;
}
};
int main(){
int n,m;cin>>n>>m;
DSU dsu(n,m);
vector<int> LMAO;
vector<vector<int>> say(n,vector<int>(m));
for (int i = 0; i < n+1; ++i)
{
string str;cin>>str;
for (int j = 0; j < m; j++){
if (i-1>=0 && i<n){
if (str[j]=='0'){
dsu.merge({i,j},{i-1,j});
}
}
if (i<n && str[j]=='1') say[i][j]++;
if (i-1>=0 && str[j]=='1') say[i-1][j]++;
}
}
for (int i = 0; i < n; i++){
string str;cin>>str;
for (int j = 0; j <= m; j++){
if (j-1>=0 && j<m){
if (str[j]=='0'){
dsu.merge({i,j},{i,j-1});
}
}
if (j<m && str[j]=='1') say[i][j]++;
if (j-1>=0 && str[j]=='1') say[i][j-1]++;
}
}
for (int i = 0; i < n; i++){
for (int j = 0; j < m; j++){
if (say[i][j]==4) continue;
if (dsu.find({i,j})!=array<int,2>{i,j}) continue;
LMAO.push_back(dsu.sz[i][j]);
}
}
sort(LMAO.begin(), LMAO.end());
/*
cout<<LMAO.size()<<endl;
for (int i = 0; i < LMAO.size(); ++i)
{
cout<<LMAO[i]<<" ";
}
cout<<endl;
*/
if (LMAO.size()==1){
cout<<-LMAO.back()<<endl;
}
else cout<<"N/A"<<endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |