제출 #1298365

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1298365		nguyenletrung	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	580 KiB

dango_maker

#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define ins insert
#define pb push_back
#define foru(i,a,b) for(int i=a;i<=b;i++)
#define ford(i,a,b) for(int i=a;i>=b;i--)
#define pii pair<int,int>
#define pll pair<ll,ll>
//#define int ll
using namespace std;
int n,m,cnt,pr[6000005],sz1[6000005],sz2[6000005],ans;
int id[3005][3005];
char b[3005][3005];

bool vis[6000005];

int find(int u)
{
	if(u==pr[u]) return u;
	else return pr[u]=find(pr[u]);
}

void join(int u,int v)
{
	u=find(u);v=find(v);
	
	if(u==v) return;
	
	if(sz1[u]>sz1[v]) swap(u,v);
	
	pr[u]=v;
	sz1[v]+=sz1[u];
	sz2[v]+=sz2[u];
	
}

signed main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
//	freopen(".inp","r",stdin);
//	freopen(".out","w",stdout);
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			cin>>b[i][j];
			if(i>=2&&b[i][j]=='W'&&b[i-1][j]=='G'&&b[i-2][j]=='R')
			{
				cnt++;pr[cnt]=cnt;sz1[cnt]=1;
//				cout<<1<<' '<<i<<' '<<j<<'\n';
				id[i][j]=cnt;
				id[i-1][j]=cnt;
				id[i-2][j]=cnt;
			}
		}
	}
	
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			if(j>=2&&b[i][j]=='W'&&b[i][j-1]=='G'&&b[i][j-2]=='R')
			{
				cnt++;pr[cnt]=cnt;sz2[cnt]=1;
//				cout<<2<<' '<<i<<' '<<j<<'\n';
				
				if(id[i][j]!=0)
				join(id[i][j],cnt);
				
				if(id[i][j-1]!=0)
				join(id[i][j-1],cnt);
				
				if(id[i][j-2]!=0)
				join(id[i][j-2],cnt);
			}
		}
	}
	
	for(int i=1;i<=cnt;i++)
	{
		int j=find(i);
		if(!vis[j])
		{
//			cout<<j<<endl;
			vis[j]=true;
			ans+=max(sz1[j],sz2[j]);
		}
	}
	
	cout<<ans;
}
/*
em thi cho du co khoc
cung se den ngay phai quen
thien duong van cho ngay em den
*/

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67