Submission #609224

#	Time	Username	Problem	Language	Result	Execution time	Memory
609224		urosk	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	151 ms	262144 KiB

dango_maker

#define here cerr<<"===========================================\n"
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll int
#define llinf 100000000000000000LL // 10^17
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define endl '\n'
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) (ll)(a.size())
#define all(a) a.begin(),a.end()
#define ceri(a,l,r) {for(ll i_ = l;i_<=r;i_++) cerr<<a[i_]<< " ";cerr<<endl;}
#define daj_mi_malo_vremena ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);

using namespace std;
using namespace __gnu_pbds;
/*
ll add(ll x,ll y){
    x+=y;
    if(x<0){
        x%=mod;
        x+=mod;
    }else{
        if(x>=mod) x%=mod;
    }
    return x;
}
ll mul(ll a,ll b){
	ll ans = (a*b)%mod;
	if(ans<0) ans+=mod;
	return ans;
}
*/
typedef tree<int,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
typedef tree<int,null_type,less_equal<ll>,rb_tree_tag,tree_order_statistics_node_update> ordered_multiset;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ll rnd(ll l,ll r){
    return uniform_int_distribution<ll>(l,r)(rng);
}
#define maxn 3005
#define maxx 10000005
ll n,m;
bool vis[maxx];
ll a[maxn][maxn];
ll id[maxn][maxn][2];
ll col[maxx];
ll it = 1;
bool okright(ll i,ll j){
    if(j+2>m) return 0;
    return (a[i][j]==1)&&(a[i][j+1]==2)&&(a[i][j+2]==3);
}
bool okdown(ll i,ll j){
    if(i+2>n) return 0;
    return (a[i][j]==1)&&(a[i+1][j]==2)&&(a[i+2][j]==3);
}
bool valid(ll i,ll j){
    return i>=1&&i<=n&&j>=1&&j<=m;
}
vector<ll> g[maxx];
pll dfs(ll u,ll par){
    //cerr<<u<<endl;
    vis[u] = 1;
    col[u] = col[par]^1;
    pll p = {1,(col[u]==1)};
    for(ll s : g[u]){
        if(s==par) continue;
        pll q = dfs(s,u);
        p.fi+=q.fi;
        p.sc+=q.sc;
    }
    return p;
}
ll ans = 0;
int main(){
	daj_mi_malo_vremena
    cin >> n >> m;
    for(ll i = 1;i<=n;i++){
        string s; cin >> s;
        for(ll j = 1;j<=m;j++){
            if(s[j-1]=='R') a[i][j] = 1;
            if(s[j-1]=='G') a[i][j] = 2;
            if(s[j-1]=='W') a[i][j] = 3;
        }
    }
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            if(a[i][j]!=1) continue;
            if(okright(i,j)) id[i][j][1] = it++;
            if(okdown(i,j)) id[i][j][0] = it++;
            if(id[i][j][1]&&id[i][j][0]){g[id[i][j][1]].pb(id[i][j][0]); g[id[i][j][0]].pb(id[i][j][1]);}
        }
    }
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++){
            if(a[i][j]!=1) continue;
            for(ll e = 1;e<=2;e++){
                for(ll k = 0;k<=0;k++){
                    if(valid(i-e,j+e)&&id[i-e][j+e][k]&&id[i][j][k^1]) g[id[i][j][k^1]].pb(id[i-e][j+e][k]);
                }
            }
            for(ll e = -2;e<=-1;e++){
                for(ll k = 1;k<=1;k++){
                    if(valid(i-e,j+e)&&id[i-e][j+e][k]&&id[i][j][k^1]) g[id[i][j][k^1]].pb(id[i-e][j+e][k]);
                }
            }
        }
    }
    /*
    here;
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++) cerr<<id[i][j][0]<< " ";
        cerr<<endl;
    }
    here;
    for(ll i = 1;i<=n;i++){
        for(ll j = 1;j<=m;j++) cerr<<id[i][j][1]<< " ";
        cerr<<endl;
    }
    here;
    */
    for(ll i = 1;i<=it-1;i++){
        if(vis[i]) continue;
        //cerr<<"i: "<<i<<endl;
        pll p = dfs(i,i);
        ans+=max(p.fi-p.sc,p.sc);
    }
    cout<<ans<<endl;
	return 0;
}
/*
5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
4 4
RGWR
GRRG
WGGW
WWWR
3 4
RGWR
GRGG
RGWW
*/

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