Submission #1087429

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087429		dpsaveslives	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	112 ms	211976 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3001;
char grid[MAXN][MAXN];
int mp[MAXN][MAXN][2];
vector<int> adj[MAXN*MAXN];
vector<bool> vis;
int side1 = 0, side2 = 0;
void dfs(int u, int s){
    vis[u] = true;
    if(s == 1){
        ++side1;
    }
    else{
        ++side2;
    }
    for(auto v : adj[u]){
        if(!vis[v]){
            dfs(v,3-s);
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int N,M; cin >> N >> M;
    for(int i = 0;i<N;++i){
        for(int j = 0;j<M;++j){
            cin >> grid[i][j];
        }
    }
    int n = 0;
    for(int i = 0;i<N;++i){
        for(int j = 0;j<M;++j){
            if(grid[i][j] == 'R'){
                if(i+2 < N && grid[i+1][j] == 'G' && grid[i+2][j] == 'W'){
                    ++n;
                    mp[i][j][1] = n;
                    //cout << i << " " << j << " " << 1 << "\n";
                }
                if(j+2 < M && grid[i][j+1] == 'G' && grid[i][j+2] == 'W'){
                    ++n;
                    mp[i][j][0] = n;
                    //cout << i << " " << j << " " << 0 << "\n";
                    if(mp[i][j][1]){
                        adj[n].push_back(mp[i][j][1]);
                        adj[mp[i][j][1]].push_back(n);
                    }
                    if(i-1 >= 0 && mp[i-1][j+1][1]){
                        adj[n].push_back(mp[i-1][j+1][1]);
                        adj[mp[i-1][j+1][1]].push_back(n);
                    }
                    if(i-2 >= 0 && mp[i-2][j+2][1]){
                        adj[n].push_back(mp[i-2][j+2][1]);
                        adj[mp[i-2][j+2][1]].push_back(n);
                    }
                }

            }
        }
    }
    vis = vector<bool>(n+1,false);
    int ans = 0;
    for(int i = 1;i<=n;++i){
        if(!vis[i]){
            side1 = 0; side2 = 0;
            dfs(i,1);
            ans += max(side1,side2);
        }
    }
    cout << ans << "\n";
    return 0;
}

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