#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXM = 50;
int N, M;
int A[MAXN+10][MAXM+10];
vector<pii> R[MAXN+10];
struct UF
{
int par[MAXM*2+10];
void init()
{
for(int i=1; i<=M+M; i++) par[i]=i;
}
int Find(int x)
{
if(x>M+M) while(1);
if(x==par[x]) return x;
return par[x]=Find(par[x]);
}
void Union(int x, int y)
{
//if(x>M+M) while(1);
//if(y>M+M) while(1);
x=Find(x); y=Find(y);
if(x==y) return;
if(x>y) swap(x, y);
par[x]=y;
}
}uf;
ll ans=0;
int main()
{
srand(time(NULL));
scanf("%d%d", &N, &M);
for(int i=1; i<=N; i++) for(int j=1; j<=M; j++)
{
scanf("%1d", &A[i][j]);
//A[i][j]=rand()%2;
}
for(int i=1; i<=N; i++)
{
R[i].push_back({0, 0});
int l, r;
int cnt=1;
for(int j=1; j<=M; j++)
{
if(!A[i][j-1] && A[i][j]) l=j;
if(A[i][j] && !A[i][j+1])
{
r=j;
R[i].push_back({l, r});
for(int k=l; k<=r; k++) A[i][k]=cnt;
if(cnt>M) while(1);
cnt++;
}
}
}
ll val=0;
vector<pair<int, pii>> V;
for(int i=1; i<=N; i++)
{
vector<pair<int, pii>> V2;
uf.init();
for(int k=1; k<R[i].size(); k++)
{
int l=R[i][k].first, r=R[i][k].second;
vector<int> t;
for(int j=l; j<=r; j++)
{
if(A[i-1][j]) t.push_back(A[i-1][j]);
}
if(t.empty()) continue;
t.erase(unique(t.begin(), t.end()), t.end());
for(int j=1; j<t.size(); j++)
{
assert(t[0]<=M+M);
assert(t[j]<=M+M);
if(uf.Find(t[0])!=uf.Find(t[j]))
{
uf.Union(t[0], t[j]);
val-=i-1;
}
}
}
for(auto it : V)
{
assert(it.second.first<=M+M);
assert(it.second.second<=M+M);
if(uf.Find(it.second.first)==uf.Find(it.second.second))
{
val+=it.first;
}
else
{
uf.Union(it.second.first, it.second.second);
}
}
//printf("!%lld\n", val);
val+=R[i].size()-1;
for(int k=1; k<R[i].size(); k++)
{
int l=R[i][k].first, r=R[i][k].second;
bool flag=true;
for(int j=l; j<=r; j++)
{
if(A[i-1][j]) flag=false;
}
if(flag) val+=i-1;
}
uf.init();
for(int k=1; k<R[i-1].size(); k++)
{
int l=R[i-1][k].first, r=R[i-1][k].second;
vector<int> t;
for(int j=l; j<=r; j++)
{
if(A[i][j]) t.push_back(A[i][j]);
}
if(t.empty()) continue;
t.erase(unique(t.begin(), t.end()), t.end());
for(int j=0; j<t.size(); j++)
{
uf.Union(k, t[j]+M);
}
for(int j=1; j<t.size(); j++)
{
V2.push_back({i-1, {t[0], t[j]}});
}
}
for(auto it : V)
{
assert(it.second.first<=M+M);
assert(it.second.second<=M+M);
if(uf.Find(it.second.first)!=uf.Find(it.second.second))
{
if(uf.Find(it.second.first)>M && uf.Find(it.second.second)>M)
{
V2.push_back({it.first, {it.second.first-M, it.second.second-M}});
uf.Union(it.second.first, it.second.second);
}
}
}
V=V2;
ans+=val;
//printf("%lld\n", val);
}
printf("%lld\n", ans);
}
Compilation message
raspad.cpp: In function 'int main()':
raspad.cpp:80:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
80 | for(int k=1; k<R[i].size(); k++)
| ~^~~~~~~~~~~~
raspad.cpp:90:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
90 | for(int j=1; j<t.size(); j++)
| ~^~~~~~~~~
raspad.cpp:118:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
118 | for(int k=1; k<R[i].size(); k++)
| ~^~~~~~~~~~~~
raspad.cpp:129:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
129 | for(int k=1; k<R[i-1].size(); k++)
| ~^~~~~~~~~~~~~~
raspad.cpp:139:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
139 | for(int j=0; j<t.size(); j++)
| ~^~~~~~~~~
raspad.cpp:143:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
143 | for(int j=1; j<t.size(); j++)
| ~^~~~~~~~~
raspad.cpp:44:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
44 | scanf("%d%d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~
raspad.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
47 | scanf("%1d", &A[i][j]);
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Execution timed out |
6042 ms |
2668 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Execution timed out |
6042 ms |
2668 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
107 ms |
16108 KB |
Output is correct |
| 2 |
Incorrect |
227 ms |
32364 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
2 ms |
2668 KB |
Output is correct |
| 2 |
Execution timed out |
6042 ms |
2668 KB |
Time limit exceeded |
| 3 |
Halted |
0 ms |
0 KB |
- |
