Submission #1068231

#	Time	Username	Problem	Language	Result	Execution time	Memory
1068231		epicci23	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	3420 KiB

dango_maker

#include "bits/stdc++.h"
//#define int long long
#define all(v) v.begin() , v.end()
//#define sz(a) (int)a.size()
using namespace std;

const int N = 3005;
pair<int,int> par[N][N];
array<int,3> sz[N][N];

pair<int,int> find(int a,int b){
  if(par[a][b]==make_pair(a,b)) return make_pair(a,b);
  return par[a][b]=find(par[a][b].first,par[a][b].second); 
}

void merge(int a,int b,int c,int d){
  auto x=find(a,b);
  auto y=find(c,d);
  a=x.first,b=x.second,c=y.first,d=y.second;
  if(make_pair(a,b)==make_pair(c,d)) return;
  if(sz[a][b][0]+sz[a][b][1]+sz[a][b][2]<sz[c][d][0]+sz[c][d][1]+sz[c][d][2]){
  	swap(a,c);
  	swap(b,d);
  }
  par[c][d]=par[a][b];
  for(int j=0;j<3;j++) sz[a][b][j]+=sz[c][d][j];
}

void _(){
  int n,m;
  cin >> n >> m;
  vector<string> v;
  for(int i=0;i<n;i++){
  	string s;cin >> s;
  	v.push_back(s);
  	for(int j=0;j<m;j++){
  	  par[i][j]=make_pair(i,j);
  	  if(s[j]=='R') sz[i][j][0]++;
  	  else if(s[j]=='G') sz[i][j][1]++;
  	  else sz[i][j][2]++;
  	}
  }
  for(int i=0;i<n;i++){
  	for(int j=0;j<m;j++){
     if(v[i][j]!='R') continue;
     if(j+2<m && v[i][j+1]=='G' && v[i][j+2]=='W'){
       merge(i,j,i,j+1);
       merge(i,j,i,j+2);
     }
     if(i+2<n && v[i+1][j]=='G' && v[i+2][j]=='W'){
       merge(i,j,i+1,j);
       merge(i,j,i+2,j);
     }
  	}
  }
  bitset<N> bs[N];
  int ans=0;
  for(int i=0;i<n;i++){
  	for(int j=0;j<m;j++){
  	  pair<int,int> c=find(i,j);
  	  int a=c.first,b=c.second;
      //cout << i << ' ' << j << ' ' << a << ' ' << b << '\n';
  	  if(bs[a][b]) continue;
  	  bs[a][b]=1;
      ans+=min({sz[a][b][0],sz[a][b][1],sz[a][b][2]});
  	}
  }
  cout << ans << '\n';
}

int32_t main(){
  cin.tie(0); ios::sync_with_stdio(0);
  int tc=1;//cin >> tc;
  while(tc--) _();
  return 0;
}

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