제출 #480282

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
480282		MOUF_MAHMALAT	Raspad (COI17_raspad)	C++14	26 / 100	333 ms	1100 KiB

raspad

#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;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 0 / 35
• Subtask 4: 0 / 39