Submission #1289596

#	Time	Username	Problem	Language	Result	Execution time	Memory
1289596		mefe123	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	580 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;
				int l=0;
				int r=0;
				
				void ai(vector<int> &v){
					for(auto &go : v){
						cin>>go;
					}
				}
				void yesno(int k){
					if(k==1){
						cout<<"Yes";
					}
					else{
						cout<<"No";
					}
				}
				vector<int> vivi;
				void dfs(int node,vector<vector<int>> &adj,vector<int> &viss, int ayrac){
					viss[node]=1;
					
					if(node<ayrac){
						if(vivi[node]==0){
								l++;
								vivi[node]=1;
						}
					
					}
					else{
						if(vivi[node]==0){
								r++;
								vivi[node]=1;
						}
					}
					for(auto go:adj[node]){
						if(viss[go]==0){
							dfs(go,adj,viss,ayrac);
						}
					}
				}

				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;
								vis[i][j+1]=vissayac;
								vis[i][j+2]=vissayac;
								vissayac++;
								//cout<<"SS"<<i<<" "<<j<<endl;
							}
						}
					}
					vector<vector<int>> adj(n*m*2);
					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++;
								}
								int k=0;
								if(vis[i][j]!=0){
									adj[vis[i][j]].pb(vissayac);
									adj[vissayac].pb(vis[i][j]);
									k=1;
								}
								if(vis[i+1][j]!=0){
									adj[vis[i+1][j]].pb(vissayac);
									adj[vissayac].pb(vis[i+1][j]);
									k=1;
								}
								if(vis[i+2][j]!=0){
									adj[vis[i+2][j]].pb(vissayac);
									adj[vissayac].pb(vis[i+2][j]);
									k=1;
								}
								vissayac+=k;
								//cout<<"YA"<<i<<" "<<j<<endl;
							}
						}
					}
					vector<int> viss(vissayac,0);
					vivi.resize(vissayac,0);
					for(int i=1;i<ayrac;i++){
						if(viss[i]==0){
							l=0;
							r=0;
							dfs(i,adj,viss,ayrac);
							if(l<r){
								cevap-=l;
								cevap+=r;
							}
						}	
					}
				
					cout<<cevap;

				}

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

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