제출 #1370259

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1370259		eyadooz	Zoo (COCI19_zoo)	C++20	0 / 110	0 ms	344 KiB

zoo

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define endl '\n'

int par[2000005]={}, siz[2000005]={};
int cmp=0;
int find(int x) {
    if(par[x]==x) return x;
    return par[x]=find(par[x]);
}
void merge(int x, int y) {
    x=find(x), y=find(y);
    if(x==y) return;
    if(siz[x]>siz[y]) swap(x, y);
    siz[y]+=siz[x];
    par[x]=y;
    cmp--;
}
int main()
{
    cin.tie(0) -> sync_with_stdio(0);

    int n, m;
    cin >> n >> m;
    for(int i = 0;i < n*m;i++) par[i]=i, siz[i]=1;
    cmp=n*m;
    string a[n];
    int val[n][m];
    int cnt=0;
    for(int i = 0;i < n;i++) for(int j = 0;j < m;j++) val[i][j]=cnt, cnt++;
    for(auto& i : a) cin >> i;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j]=='*') cmp--;
            if(i+1<n&&a[i][j]==a[i+1][j]&&a[i][j]!='*') merge(val[i][j], val[i+1][j]);
            if(j+1<m&&a[i][j]==a[i][j+1]&&a[i][j]!='*') merge(val[i][j], val[i][j+1]);
        }
    }
    cout << cmp;
}

• 서브태스크 1: 0 / 45
• 서브태스크 2: 0 / 65