Submission #208110

#	Time	Username	Problem	Language	Result	Execution time	Memory
208110		dOAOb	Zoo (COCI19_zoo)	C++14	0 / 110	5 ms	380 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];
bool visch[mxsz*mxsz];
bool vis[mxsz][mxsz];

int N, M;
inline int fid(int i, int j)
{
	return i*M+j;
}

int dfs(int i, int j, int dep, DSU &dsu)
{
	auto chid = [&](int i, int j)
	{
		return dsu.find(fid(i, j));
	};
	
	visch[chid(i, j)] = vis[i][j] = 1;
	
	int mxn = dep;
	for (int vi=-1; vi<=1; vi++)
		for (int vj=-1; vj<=1; vj++)
			if ((vi!=0) ^ (vj!=0))
			{
				int ni = i+vi, nj = j+vj;
				if (0<=ni && ni<N && 0<=nj && nj<M && v[ni][nj]!='*' && !vis[ni][nj] && (chid(i, j)==chid(ni, nj) || !visch[chid(ni, nj)]))
				{
					int vd = dsu.find(fid(i, j))!=dsu.find(fid(ni, nj));
					mxn = max(mxn, dfs(ni, nj, dep+vd, dsu));
				}
			}
	return mxn;
}

signed main()
{
	ndbg( ios::sync_with_stdio(0); cin.tie(0); );
	int n, m; cin>>n>>m, N = n, M = m;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			cin>>v[i][j];
	
	DSU dsu(n*m);
	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));
		}
	
	cout<<dfs(0, 0, 1, dsu)<<'\n';
}

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