제출 #480282

#제출 시각아이디문제언어결과실행 시간메모리
480282MOUF_MAHMALATRaspad (COI17_raspad)C++14
26 / 100
333 ms1100 KiB
#include<bits/stdc++.h> #define all(s) s.begin(),s.end() #define F first #define S second using namespace std; typedef int ll; ll n,m,ans,x,p[50009]; bool b[1005][55]; char c; ll gp(ll z) { if(p[z]==z) return z; return p[z]=gp(p[z]); } void mrg(ll xo,ll yo) { xo=gp(xo),yo=gp(yo); if(xo==yo) return; x--; p[yo]=xo; } int main() { ios_base::sync_with_stdio(0); cin.tie(0),cout.tie(0); cin>>n>>m; for(ll i=0; i<n; i++) for(ll j=0; j<m; j++) { cin>>c; b[i][j]=c-'0'; } for(ll i=0; i<n; i++) { x=0; for(ll j=0; j<m; j++) if(b[i][j]) { p[i*m+j]=i*m+j; x++; if(b[i][j-1]) mrg(i*m+j-1,i*m+j); } ans+=x; for(ll j=i+1; j<n; j++) { for(ll k=0; k<m; k++) { if(b[j][k]) { p[j*m+k]=j*m+k; x++; if(b[j][k-1]) mrg(j*m+k-1,j*m+k); if(b[j-1][k]) mrg(j*m+k-m,j*m+k); } } ans+=x; } } cout<<ans; return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...