Submission #1309349

#	Time	Username	Problem	Language	Result	Execution time	Memory
1309349		itstryhard	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	584 KiB

dango_maker

#include <iostream>
#include <vector>
#include <array>
#include <algorithm>

using namespace std;

int n, m;
vector<vector<int>> grid;

vector<vector<bool>> horizontal;
vector<vector<bool>> vertical;

vector<vector<array<bool, 2>>> checked;

struct Dango{
    int x;
    int y;
    int d; // 0 = vertical, 1 = horizontal

    bool operator<(Dango other){
        if (x == other.x){
            return d < other.d;
        }
        return x < other.x;
    }
};

vector<Dango> now;

void grow(int x, int y, int d){
    checked[y][x][d] = true;
    now.push_back(Dango{x, y, d});

    if (d == 1){
        if (y-1 >= 0 && x+1 < m && vertical[y-1][x+1] && !checked[y-1][x+1][!d]){
            grow(x+1, y-1, !d);
        }
        if (vertical[y][x] && !checked[y][x][!d]){
            grow(x, y, !d);
        }
        if (x-1 >= 0 && y+1 < n && vertical[y+1][x-1] && !checked[y+1][x-1][!d]){
            grow(x-1, y+1, !d);
        }
    }
    if (d == 0){
        if (y-1 >= 0 && x+1 < m && horizontal[y-1][x+1] && !checked[y-1][x+1][!d]){
            grow(x+1, y-1, !d);
        }
        if (horizontal[y][x] && !checked[y][x][!d]){
            grow(x, y, !d);
        }
        if (x-1 >= 0 && y+1 < n && horizontal[y+1][x-1] && !checked[y+1][x-1][!d]){
            grow(x-1, y+1, !d);
        }
    }
}

int ile(){
    sort(now.begin(), now.end());

    int w = 1;
    array<bool, 2> best = {false, false};

    best[now[0].d] = true;

    for (int i=1; i<size(now); i++){
        int d = now[i].d;

        if (best[d]){
            w++;
            best = {false, false};
        }
        else{
            best[d] = true;
        }
    }

    return w;
}

int main(){
    cin >> n >> m;

    checked = vector<vector<array<bool, 2>>>(n, vector<array<bool, 2>>(m, {false, false}));

    for (int i=0; i<n; i++){
        grid.push_back(vector<int> {});

        for (int j=0; j<m; j++){
            char a;
            cin >> a;

            if (a == 'R'){
                grid[i].push_back(0);
            }
            if (a == 'G'){
                grid[i].push_back(1);
            }
            if (a == 'W'){
                grid[i].push_back(2);
            }
        }
    }


    if (m >= 3){
        for (int j=0; j<n; j++){
            horizontal.push_back(vector<bool> {false});

            for (int i=1; i<m-1; i++){
                if (grid[j][i-1] == 0 && grid[j][i] == 1 && grid[j][i+1] == 2){
                    horizontal[j].push_back(true);
                }
                else{
                    horizontal[j].push_back(false);
                }
            }

            horizontal[j].push_back(false);
        }
    } 


    if (n >= 3){
        vertical.push_back(vector<bool> {});
        for (int i=0; i<m; i++){
            vertical[0].push_back(false);
        }


        for (int j=1; j<n-1; j++){
            vertical.push_back(vector<bool> {});

            for (int i=0; i<m; i++){
                if (grid[j-1][i] == 0 && grid[j][i] == 1 && grid[j+1][i] == 2){
                    vertical[j].push_back(true);
                }
                else{
                    vertical[j].push_back(false);
                }
            }
        }


        vertical.push_back(vector<bool> {});
        for (int i=0; i<m; i++){
            vertical[n-1].push_back(false);
        }
    }



    if (m < 3 && n < 3){
        cout << 0;
        return 0;
    }

    if (m < 3){
        int w = 0;
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (vertical[i][j]){
                    w++;
                }
            }
        }

        cout << w;
        return 0;
    }


    if (n < 3){
        int w = 0;
        for (int i=0; i<n; i++){
            for (int j=0; j<m; j++){
                if (horizontal[i][j]){
                    w++;
                }
            }
        }

        cout << w;
        return 0;
    }




    int wynik = 0;


    for (int i=0; i<n; i++){
        for (int j=0; j<m; j++){
            if (vertical[i][j] && !checked[i][j][0]){
                grow(j, i, 0);
                wynik += ile();
                now.clear();
            }
            if (horizontal[i][j] && !checked[i][j][1]){
                grow(j, i, 1);
                wynik += ile();
                now.clear();
            }
        }
    }
    cout << wynik;
}

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