Submission #241657

#	Time	Username	Problem	Language	Result	Execution time	Memory
241657		dsjong	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	6 ms	384 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
set<int>node[100];
bool vis[100];
char a[15][15];
vector<int>adj[100];
int odd, even;
void dfs(int x, int p){
	if(p%2==1) odd++;
	else even++;
	vis[x]=true;
	for(int y:adj[x]){
		if(vis[y]) continue;
		dfs(y, 1-p);
	}
}
int main(){
	int n, m;
	cin>>n>>m;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin>>a[i][j];
		}
	}
	int cnt=0;
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			string s="";
			if(j+2<m){
				s=(s+a[i][j]+a[i][j+1]+a[i][j+2]);
				//cout<<s<<endl;
				if(s=="RGW"){
					node[cnt].insert(i*m+j);
					node[cnt].insert(i*m+j+1);
					node[cnt].insert(i*m+j+2);
					cnt++;
				}
			}
			if(i+2<n){
				s="";
				s=s+a[i][j]+a[i+1][j]+a[i+2][j];
				//cout<<s<<endl;
				if(s=="RGW"){
					node[cnt].insert(i*m+j);
					node[cnt].insert((i+1)*m+j);
					node[cnt].insert((i+2)*m+j);
					cnt++;
				}
			}
		}
	}
	for(int i=0;i<cnt;i++){
		for(int j=i+1;j<cnt;j++){
			set<int>s;
			for(int k:node[i]) s.insert(k);
			for(int k:node[j]) s.insert(k);
			if((int)s.size()!=6){
				adj[i].push_back(j);
				adj[j].push_back(i);
			}
		}
	}
	int ans=0;
	for(int i=0;i<cnt;i++){
		if(vis[i]) continue;
		odd=0, even=0;
		dfs(i, 0);
		ans+=max(odd, even);
	}
	cout<<ans;
}

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