oj.uz

Submission #208105

# Submission time Handle Problem Language Result Execution time Memory
208105 2020-03-10T03:48:40 Z dOAOb Zoo (COCI19_zoo) C++14
0 / 110
 5 ms 376 KB 
#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);
	
//	for (int i=0;i<n;i++)
//		for (int j=0;j<m;j++)
//		{
//			if (v[i][j]!='*') cout<<dsu.find(fid(i, j))<<" \n"[j==m-1];
//			else cout<<"-1"<<" \n"[j==m-1];
//		}
	
//	cout<<"##"<<sum<<'\n';
	cout<<min(sum, 3LL)<<'\n';
}

Subtask #1
0 / 45.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 65.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -