제출 #666519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
666519		manizare	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	124 ms	235520 KiB

dango_maker

#include <bits/stdc++.h>
#define all(a) a.begin(),a.end() 
#define pb push_back
using namespace std ;
const int maxn = 3002 , maxq =1e6 , inf = 1e9 + 100 , mod = 1e9 + 7 ;
char c[maxn][maxn] ;
vector <int> G[maxq] ;
vector <int> vec[maxn][maxn] ;
int ans[2] ;
bool mark[maxq] ;
void dfs(int v , int k){
	mark[v] = 1;
	ans[k]++;
	for(int i = 0 ; i < (int)G[v].size() ; i++){
		int u = G[v][i] ;
		if(mark[u] == 1)continue ;
		dfs(u , k^1);  
	}
}

signed main(){
	int n , m ;
	cin >> n >> m ;
	for(int i = 1; i <= n ; i++){
		for(int j = 1; j <= m ; j++){
			cin >> c[i][j] ;
		}
	}
	int cnt = 0 ;
	for(int i =1 ; i <= n ; i++){
		for(int j = 1; j <= m ; j++){
			if(i <= (n-2) && c[i][j] == 'R' && c[i+1][j] == 'G' && c[i+2][j] == 'W'){
				cnt++;
				vec[i][j].pb(cnt);
				vec[i+1][j].pb(cnt);
				vec[i+2][j].pb(cnt);
			}
			if(j <= (m-2) && c[i][j] == 'R' && c[i][j+1] == 'G' && c[i][j+2] == 'W'){
				cnt++;
				vec[i][j].pb(cnt);
				vec[i][j+1].pb(cnt);
				vec[i][j+2].pb(cnt);
			}
		}
	}
	for(int i =1 ; i<= n ; i++){
		for(int j = 1; j <= m ; j++){
			if(vec[i][j].size() == 2){
				int v = vec[i][j][0] , u = vec[i][j][1] ;
				G[v].pb(u);
				G[u].pb(v);
			}
		}
	}
	int ans1 = 0 ;
	for(int i = 1 ;i <=  cnt ; i++){
		if(mark[i] == 1)continue ;
		dfs(i , 0);
		ans1 += max(ans[1] , ans[0]);
		ans[0] = ans[1] =0 ;
	}
	cout << ans1 << "\n";
}

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