제출 #208106

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
208106		dOAOb	Zoo (COCI19_zoo)	C++14	0 / 110	5 ms	376 KiB

zoo

#include<iostream>
#include<algorithm>
#include<numeric>
#include<queue>
#include<tuple>
#include<map>
#include<set>
using namespace std;

#define int long long

#ifdef lioraju
	#define ndbg(x) 
#else
	#define ndbg(x) x
#endif

struct DSU
{
	vector<int> p;
	inline int find(int n) { return p[n]==n? n: p[n]=find(p[n]); }
	inline void join(int a, int b) { p[find(a)] = find(b); }
	DSU(int n): p(n) { iota(p.begin(), p.end(), 0LL); }
};

const int mxsz = 1e3 + 5;

char v[mxsz][mxsz];

signed main()
{
	ndbg( ios::sync_with_stdio(0); cin.tie(0); );
	int n, m; cin>>n>>m;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			cin>>v[i][j];
	
	DSU dsu(n*m);
	auto fid = [&](int i, int j)
	{
		return i*m+j;
	};
	
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			if (v[i][j]=='*') continue;
			
			if (i+1<n && v[i+1][j]==v[i][j]) dsu.join(fid(i, j), fid(i+1, j));
			if (j+1<m && v[i][j+1]==v[i][j]) dsu.join(fid(i, j), fid(i, j+1));
		}
	
	int sum = 0;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (v[i][j]!='*') sum += dsu.find(fid(i, j)) == fid(i, j);
	
	cout<<sum<<'\n';
}

• Subtask 1: 0 / 45
• Subtask 2: 0 / 65