제출 #1289578

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

dango_maker

			#include <iostream> 
			#include <vector> 
			#include <string> 
			#include <algorithm>
			#include <cmath> 
			#include <map>			
			#include <set>
			#include <queue>	
			#include <stack>
			#include <unordered_map>
			#include <unordered_set>
			#include <bitset>
			#include <numeric> 
			#include <functional>
			#include <iomanip>
			#include <sstream>


			#define int long long
			#define pb push_back
			
			#define b begin()
			#define e end()
			#define fi first
			#define se second
			#define makep make_pair
				
			using namespace std;
			
			int mod=1e9+7;
			
			void ai(vector<int> &v){
				for(auto &go : v){
					cin>>go;
				}
			}
			void yesno(int k){
				if(k==1){
					cout<<"Yes";
				}
				else{
					cout<<"No";
				}
			}
			pair<int,int> dfs(int node,vector<vector<int>> &adj,vector<int> &viss, int ayrac,int &l,int &r){
				viss[node]=1;
				if(node<ayrac){
					l++;
				}
				else{
					r++;
				}
				for(auto go:adj[node]){
					if(viss[go]==0){
						dfs(go,adj,viss,ayrac,l,r);
					}
				}
				return {l,r};
			}

			void solve(){
				int n,m;
				cin>>n>>m;
				vector<vector<char>> arr(n,vector<char>(m));
				vector<vector<int>> vis(n,vector<int>(m));
				for(int i=0;i<n;i++){
					for(int j=0;j<m;j++){
						cin>>arr[i][j];
					}
				}
				int cevap=0;
				int vissayac=1;
				for(int i=0;i<n;i++){
					for(int j=0;j<m-2;j++){
						if(arr[i][j]=='R'&&arr[i][j+1]=='G'&&arr[i][j+2]=='W'){
							cevap++;
							vis[i][j]=vissayac;
							vissayac++;
							//cout<<"SS"<<i<<" "<<j<<endl;
						}
					}
				}
				vector<vector<int>> adj(n*n);
				int ayrac=vissayac;
				for(int j=0;j<m;j++){
					for(int i=0;i<n-2;i++){
						if(arr[i][j]=='R'&&arr[i+1][j]=='G'&&arr[i+2][j]=='W'){
							if(vis[i][j]==0&&vis[i+1][j]==0&&vis[i+2][j]==0){
								cevap++;
							}
						
							if(vis[i][j]!=0){
								adj[vis[i][j]].pb(vissayac);
								adj[vissayac].pb(vis[i][j]);
								vissayac++;
							}
							if(vis[i+1][j]!=0){
								adj[vis[i+1][j]].pb(vissayac);
								adj[vissayac].pb(vis[i+1][j]);
								vissayac++;
							}
							if(vis[i+2][j]!=0){
								adj[vis[i+2][j]].pb(vissayac);
								adj[vissayac].pb(vis[i+2][j]);
								vissayac++;
							}
					
							//cout<<"YA"<<i<<" "<<j<<endl;
						}
					}
				}
				vector<int> viss(vissayac,0);
				for(int i=1;i<ayrac;i++){
					if(viss[i]==0){
						int l=0;
						int r=0;
						pair<int,int> mima=dfs(i,adj,viss,ayrac,l,r);
						if(mima.first<mima.second){
							cevap-=mima.first;
							cevap+=mima.second;
						}
					}	
				}
			
				cout<<cevap;

			}

			signed main(){
				ios::sync_with_stdio(false);
				cin.tie(nullptr);
				int t=1;
				//cin>>t;
				while(t--){
					solve();
				}
			}

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