#include<stdio.h>
#include<vector>
#define MAX 5005005
#define grid(i,j) ((i)*M+(j))
using namespace std;
typedef long long lld;
int N, M; char mp[101010][55];
int tmp[MAX]; // always be 0
int cnum[101010][55];
struct uftree {
int par[MAX], gas[MAX], ccn;
int us[55], ucn;
void init(int st, int en){
for(int i=st; i<en; i++) par[i]=-1, gas[i]=0;
ccn=0;
}
void set_us(const char* c, int row, int wid){
ucn=0;
for(int i=0; i<wid; i++){
if(c[i]=='0') continue;
if(i && c[i-1]=='1') continue;
us[ucn++] = grid(row, i);
}
}
void add(int ix){ par[ix]=-1; gas[ix]=1; ccn++; }
int root(int ix){ return par[ix]<0 ? ix : par[ix]=root(par[ix]); }
void connect(int n1, int n2){
n1 = root(n1), n2 = root(n2);
if(n1 == n2) return;
if(gas[n1] > gas[n2]) par[n2]=n1, gas[n1]+=gas[n2];
else par[n1]=n2, gas[n2]+=gas[n1];
ccn--;
}
int condition(int* vs){
int cnt=0;
for(int i=0; i<ucn; i++){
int r = root(us[i]);
if(tmp[r]) vs[i]=tmp[r]-1;
else vs[i]=-1, tmp[r]=i+1, cnt++;
}
for(int i=0; i<ucn; i++) tmp[root(us[i])]=0;
return cnt;
}
} up, dw;
int par[55], ccn;
int rt(int ix){ return par[ix]<0 ? ix : par[ix]=rt(par[ix]); }
lld dnq(int s, int e){
int m = (s+e)/2; lld gap=0, cr=0;
if(s > e) return 0;
if(s == e){
up.set_us(mp[s], s, M);
return up.ucn;
}
gap = dnq(s, m-1) + dnq(m+1, e);
up.init(grid(s,0), grid(m+1,0));
up.set_us(mp[m], m, M);
for(int i=m; i>=s; i--){
for(int j=0; j<M; j++){
if(mp[i][j]=='0')continue;
up.add(grid(i,j));
if(i<m && mp[i+1][j]=='1') up.connect(grid(i,j), grid(i+1,j));
if(j>0 && mp[i][j-1]=='1') up.connect(grid(i,j), grid(i,j-1));
}
cr += (lld)(e-m+1) * (up.ccn - up.condition(cnum[i]));
}
dw.init(grid(m,0), grid(e+1,0));
dw.set_us(mp[m], m, M);
for(int i=m; i<=e; i++){
for(int j=0; j<M; j++){
if(mp[i][j]=='0')continue;
dw.add(grid(i,j));
if(i>m && mp[i-1][j]=='1') dw.connect(grid(i,j), grid(i-1,j));
if(j>0 && mp[i][j-1]=='1') dw.connect(grid(i,j), grid(i,j-1));
}
cr += (lld)(m-s+1) * (dw.ccn - dw.condition(cnum[i]));
}
int ucn=1, uix[55]={m,}, dcn=1, dix[55]={m,}; vector<int> modi[55];
for(int i=m-1; i>=s; i--){
int j;
for(j=0; j<up.ucn; j++) if(cnum[i][j]!=cnum[i+1][j]) break;
if(j<up.ucn) uix[ucn++]=i;
}
uix[ucn++]=s-1;
for(int i=m+1; i<=e; i++){
int j, fl=0;
for(j=0; j<dw.ucn; j++){
if(cnum[i-1][j]<0 && cnum[i][j]>=0) fl=1, modi[dcn].push_back(j);
}
if(fl) dix[dcn++]=i;
}
dix[dcn++]=e+1;
for(int i=0; i<ucn-1; i++){
ccn = up.ucn;
for(int j=0; j<up.ucn; j++){
par[j] = cnum[uix[i]][j];
if(par[j]>=0) ccn--;
}
for(int j=0; j<dcn-1; j++){
for(int k=modi[j].size(); k--;){
int a=modi[j][k], b=cnum[uix[j]][a];
a=rt(a), b=rt(b);
if(a!=b) par[b]=a, ccn--;
}
cr += (lld)(uix[i]-uix[i+1])*(dix[j+1]-dix[j])*ccn;
}
}
return gap+cr;
}
int main(){
scanf("%d%d\n", &N, &M);
for(int i=0; i<N; i++) gets(mp[i]);
printf("%lld\n", dnq(0, N-1));
return 0;
}
Compilation message
raspad.cpp: In function 'int main()':
raspad.cpp:121:25: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
for(int i=0; i<N; i++) gets(mp[i]);
^
In file included from raspad.cpp:1:0:
/usr/include/stdio.h:638:14: note: declared here
extern char *gets (char *__s) __wur __attribute_deprecated__;
^
raspad.cpp:121:25: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
for(int i=0; i<N; i++) gets(mp[i]);
^
In file included from raspad.cpp:1:0:
/usr/include/stdio.h:638:14: note: declared here
extern char *gets (char *__s) __wur __attribute_deprecated__;
^
raspad.cpp:121:35: warning: 'char* gets(char*)' is deprecated [-Wdeprecated-declarations]
for(int i=0; i<N; i++) gets(mp[i]);
^
In file included from raspad.cpp:1:0:
/usr/include/stdio.h:638:14: note: declared here
extern char *gets (char *__s) __wur __attribute_deprecated__;
^
raspad.cpp:120:25: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d\n", &N, &M);
^
raspad.cpp:121:36: warning: ignoring return value of 'char* gets(char*)', declared with attribute warn_unused_result [-Wunused-result]
for(int i=0; i<N; i++) gets(mp[i]);
^
/tmp/ccJmEBTl.o: In function `main':
raspad.cpp:(.text.startup+0x3b): warning: the `gets' function is dangerous and should not be used.
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
186 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
413 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
0 ms |
126060 KB |
Output is correct |
| 2 |
Incorrect |
0 ms |
126060 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
