Submission #208142

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
208142	2020-03-10T05:19:56 Z	dOAOb	Zoo (COCI19_zoo)	C++14	110 / 110	341 ms	125176 KB

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.0 / 45.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	47736 KB	Output is correct
2	Correct	28 ms	47864 KB	Output is correct
3	Correct	29 ms	47864 KB	Output is correct
4	Correct	29 ms	47864 KB	Output is correct
5	Correct	30 ms	48120 KB	Output is correct
6	Correct	31 ms	48248 KB	Output is correct
7	Correct	31 ms	48120 KB	Output is correct
8	Correct	32 ms	48504 KB	Output is correct
9	Correct	32 ms	48504 KB	Output is correct
10	Correct	32 ms	48632 KB	Output is correct
11	Correct	31 ms	48504 KB	Output is correct
12	Correct	32 ms	48632 KB	Output is correct
13	Correct	31 ms	48504 KB	Output is correct
14	Correct	33 ms	48504 KB	Output is correct
15	Correct	32 ms	48376 KB	Output is correct

Subtask #2

65.0 / 65.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	28 ms	47736 KB	Output is correct
2	Correct	28 ms	47864 KB	Output is correct
3	Correct	29 ms	47864 KB	Output is correct
4	Correct	29 ms	47864 KB	Output is correct
5	Correct	30 ms	48120 KB	Output is correct
6	Correct	31 ms	48248 KB	Output is correct
7	Correct	31 ms	48120 KB	Output is correct
8	Correct	32 ms	48504 KB	Output is correct
9	Correct	32 ms	48504 KB	Output is correct
10	Correct	32 ms	48632 KB	Output is correct
11	Correct	31 ms	48504 KB	Output is correct
12	Correct	32 ms	48632 KB	Output is correct
13	Correct	31 ms	48504 KB	Output is correct
14	Correct	33 ms	48504 KB	Output is correct
15	Correct	32 ms	48376 KB	Output is correct
16	Correct	86 ms	63992 KB	Output is correct
17	Correct	87 ms	64344 KB	Output is correct
18	Correct	86 ms	64376 KB	Output is correct
19	Correct	108 ms	65784 KB	Output is correct
20	Correct	87 ms	64376 KB	Output is correct
21	Correct	330 ms	121444 KB	Output is correct
22	Correct	320 ms	120952 KB	Output is correct
23	Correct	330 ms	121976 KB	Output is correct
24	Correct	341 ms	125176 KB	Output is correct
25	Correct	333 ms	123512 KB	Output is correct
26	Correct	332 ms	122872 KB	Output is correct
27	Correct	328 ms	121080 KB	Output is correct
28	Correct	321 ms	120696 KB	Output is correct
29	Correct	335 ms	124772 KB	Output is correct
30	Correct	335 ms	123640 KB	Output is correct