Submission #208142

#	Time	Username	Problem	Language	Result	Execution time	Memory
208142		dOAOb	Zoo (COCI19_zoo)	C++14	110 / 110	341 ms	125176 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 vis[mxsz*mxsz];
int stp[mxsz*mxsz];
set<int> AE[mxsz*mxsz];

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

inline int chid(int i, int j, DSU &dsu)
{
	return dsu.find(fid(i, j));
}

int dfs(int p, int dep)
{
	vis[p] = 1;
	
	int mxn = dep;
	for (int x: AE[p])
		if (!vis[x]) mxn = max(mxn, dfs(x, dep+1));
	
	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));
		}
	
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
		{
			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]!='*' && chid(i, j, dsu)!=chid(ni, nj, dsu))
							AE[chid(i, j, dsu)].insert(chid(ni, nj, dsu));
					}
		}
	
	int st = chid(0, 0, dsu);
	queue<int> qu; vis[st]=1, stp[st]=1, qu.push(st);
	while (qu.size())
	{
		int p = qu.front(); qu.pop();
//		cout<<"##"<<p<<": "<<stp[p]<<'\n';
		
		for (int x: AE[p])
			if (!vis[x]) vis[x] = 1, stp[x]=stp[p]+1, qu.push(x);
	}
	
//	for (int i=0;i<n;i++)
//		for (int j=0;j<m;j++)
//		{
//			if (v[i][j]=='*') cout<<'-'<<" \n"[j==m-1];
//			else cout<<chid(i, j, dsu)<<" \n"[j==m-1];
//		}
	
	int mxn = 1;
	for (int i=0;i<n;i++)
		for (int j=0;j<m;j++)
			if (v[i][j]!='*') mxn = max(mxn, stp[chid(i, j, dsu)]);
	
	cout<<mxn<<'\n';
}

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