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<array<int,2>> arr;
vector<vector<int>> say(n,vector<int>(m));
vector<vector<int>> isloop(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'){
if (dsu.find({i,j})==dsu.find({i-1,j})){
isloop[dsu.find({i,j})[0]][dsu.find({i,j})[1]]=1;
}
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'){
if (dsu.find({i,j})==dsu.find({i,j-1})){
isloop[dsu.find({i,j})[0]][dsu.find({i,j})[1]]=1;
}
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;
arr.push_back({dsu.sz[i][j],isloop[i][j]});
}
}
/*
cout<<LMAO.size()<<endl;
for (int i = 0; i < LMAO.size(); ++i)
{
cout<<LMAO[i]<<" ";
}
cout<<endl;
*/
sort(arr.begin(), arr.end());
if (arr.size()==0){
cout<<0<<endl;
}
else if (arr.size()==1){
cout<<-arr.back()[0]<<endl;
}
else if (arr.size()==2){
if (arr[0][1]){
if (arr[0][0]<4){
//her seyi alcak bana buyugu vercek
cout<<arr[1][0]-arr[0][0]<<endl;
}
else {
//4 haric her seyi alcak bana 4 vercek kendi buyuk alcak
cout<<4-(arr[0][0]-4+arr[1][0])<<endl;
}
}
else {
if (arr[0][0]<2){
//her seyi alcak bana buyugu vercek
cout<<arr[1][0]-arr[0][0]<<endl;
}
else {
cout<<2-(arr[0][0]-2+arr[1][0])<<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... |