Submission #48554

#	Time	Username	Problem	Language	Result	Execution time	Memory
48554		ngkan146	Dango Maker (JOI18_dango_maker)	C++11	0 / 100	1 ms	128 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
int n,m;
string s[3005];
vector <int> G[18000005];
bool visited[18000005];
bool mark[2][3005][3005];   // 0 = down, 1 = right
int glob, cnt;
void dfs(int u, int color){
    visited[u] = 1;
    glob ++;
    cnt += (color == 0);
    for(auto v: G[u]){
        //cout << u << ' ' << v << endl;
        if (!visited[v])
            dfs(v, color ^= 1);
    }
}
int main(){
    iostream::sync_with_stdio(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++)   cin >> s[i], s[i] = '0' + s[i];
    int ans = 0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if (i <= n-2 && s[i][j] == 'R' && s[i+1][j] == 'G' && s[i+2][j] == 'W')
                mark[0][i][j] = 1;
            if (j <= m-2 && s[i][j] == 'R' && s[i][j+1] == 'G' && s[i][j+2] == 'W')
                mark[1][i][j] = 1;
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if (mark[0][i][j]){
                if (mark[1][i][j]){
                    G[(i-1) * n + j-1].push_back((i-1) * n + j-1 + n*m);
                }
                if (i < n && j > 1 && mark[1][i+1][j-1]){
                    G[(i-1) * n + j-1].push_back((i+1-1) * n + j-1-1 + n*m);
                }
            }
            if (mark[1][i][j]){
                if (mark[0][i][j]){
                    G[(i-1) * n + j-1 + n*m].push_back((i-1) * n + j-1);
                }
                if (i > 1 && j < m && mark[0][i-1][j+1]){
                    G[(i-1) * n + j-1 + n*m].push_back((i-1-1) * n + j+1-1);
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            //cout << i << ' ' << j << ' ' << mark[0][i][j] << ' ' << mark[1][i][j] << endl;
            if (mark[0][i][j] && !visited[(i-1)*n + j-1]){
                glob = cnt = 0;
                dfs((i-1)*n + j-1, 0);
                ans += max(cnt, glob-cnt);
            }
            if (mark[1][i][j] && !visited[(i-1)*n + j-1 + n*m]){
                glob = cnt = 0;
                dfs((i-1)*n + j-1 + n*m, 0);
                ans += max(cnt, glob-cnt);
            }
        }
    }
    cout << ans;
}

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