| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1068222 | epicci23 | Dango Maker (JOI18_dango_maker) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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-2;i++){
for(int j=0;j<m-2;j++){
if(v[i][j]!='R') continue;
if(v[i][j+1]=='G' && v[i][j+2]=='W'){
merge(i,j,i,j+1);
merge(i,j,i,j+2);
}
if(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;
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;
}