답안 #208142

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
208142 2020-03-10T05:19:56 Z dOAOb Zoo (COCI19_zoo) C++14
110 / 110
341 ms 125176 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];
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';
}
# 결과 실행 시간 메모리 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
# 결과 실행 시간 메모리 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