Submission #1006951

#	Time	Username	Problem	Language	Result	Execution time	Memory
1006951		Otalp	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	44 ms	218124 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
#define ll long long
#define pll pair<ll, ll>
#define pb push_back


int MAXLS = 5000000;
int dq[3010][3010];
int a[3021][3021];
int kto[9000001];
int cnt[3];
int pos[9000001];
vector<int> q[9000001];

void dfs(int v){
    pos[v] = 1;
    cnt[kto[v]] ++;
    for(int to: q[v]){
        if(pos[to]) continue;
        dfs(to);
    }
}

void add(int i, int j, int x){
    if(dq[i][j] != -1) q[dq[i][j]].pb(x), q[x].pb(dq[i][j]);
    dq[i][j] = x;
}


void solve(){   
    int n, m;
    cin>>n>>m;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            char c;
            cin>>c;
            a[i][j] = c;
            dq[i][j] = -1;
        }
    }
    int ls = 0;

    for(int i=1; i<=n; i++){
        for(int j=1; j<=m; j++){
            if(j >= 3 and a[i][j] == 'W' and a[i][j-1] == 'G' and a[i][j - 2] == 'R'){
                ls ++;
                add(i, j, ls);
                add(i, j-1, ls);
                add(i, j-2, ls);
                kto[ls] = 1;
            }
            if(i >= 3 and a[i][j] == 'W' and a[i-1][j] == 'G' and a[i-2][j] == 'R'){
                ls ++;
                add(i, j, ls);
                add(i-1, j, ls);
                add(i-2, j, ls);
                kto[ls] = 2;
            }
        }
    }
    ll ans = 0;
    //cout<<ls<<'\n';
    for(int i=1; i<=ls; i++){
        if(pos[i]) continue;
        cnt[1] = cnt[2] = 0;
        dfs(i);
        ans += max(cnt[1], cnt[2]);
    }
    cout<<ans<<'\n';
}

int main(){
    solve();
}

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