Submission #1281644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281644		SSKMF	Dango Maker (JOI18_dango_maker)	C++20	13 / 100	1 ms	588 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

char matrice[3000][3001];
bool vizitat[3000][3000] , blocat[3000][3000];

int main ()
{
    ios :: sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int linii , coloane;
    cin >> linii >> coloane;

    for (int linie = 0 ; linie < linii ; linie++)
        { cin >> matrice[linie]; }
    
    int cuplaj = 0;
    for (int linie = 0 ; linie < linii ; linie++) {
        for (int coloana = 0 ; coloana < coloane ; coloana++) {
            if (matrice[linie][coloana] == 'R' && !vizitat[linie][coloana])
            {
                int aparitii[2] = { };
                queue < pair <int , int> > ramas;
                ramas.emplace(linie , coloana); vizitat[linie][coloana] = true;
                vector < pair <int , int> > candidati;
                while (!ramas.empty())
                {
                    pair <int , int>& nod = ramas.front();
                    if (matrice[nod.first][nod.second] == 'W')
                    {
                        aparitii[0]++;
                        if (nod.first > 1 && matrice[nod.first - 1][nod.second] == 'G' && matrice[nod.first - 2][nod.second] == 'R' && !vizitat[nod.first - 2][nod.second])
                            { ramas.emplace(nod.first - 2 , nod.second); vizitat[nod.first - 2][nod.second] = true; candidati.emplace_back(nod.first - 1 , nod.second); }
                        if (nod.second > 1 && matrice[nod.first][nod.second - 1] == 'G' && matrice[nod.first][nod.second - 2] == 'R' && !vizitat[nod.first][nod.second - 2])
                            { ramas.emplace(nod.first , nod.second - 2); vizitat[nod.first][nod.second - 2] = true; candidati.emplace_back(nod.first , nod.second - 1); }
                    }
                    else
                    {
                        aparitii[1]++;
                        if (nod.first + 2 < linii && matrice[nod.first + 1][nod.second] == 'G' && matrice[nod.first + 2][nod.second] == 'W' && !vizitat[nod.first + 2][nod.second])
                            { ramas.emplace(nod.first + 2 , nod.second); vizitat[nod.first + 2][nod.second] = true; candidati.emplace_back(nod.first + 1 , nod.second); }
                        if (nod.second + 2 < coloane && matrice[nod.first][nod.second + 1] == 'G' && matrice[nod.first][nod.second + 2] == 'W' && !vizitat[nod.first][nod.second + 2])
                            { ramas.emplace(nod.first , nod.second + 2); vizitat[nod.first][nod.second + 2] = true; candidati.emplace_back(nod.first , nod.second + 1); }
                    }

                    ramas.pop();
                }

                cuplaj += min(aparitii[0] , aparitii[1]);

                if (aparitii[0] == aparitii[1])
                {
                    sort(candidati.begin() , candidati.end());
                    
                    int indice = 0;
                    for (auto& locatie : candidati) {
                        indice ^= 1;
                        if (!indice) { continue; }
                        if (blocat[locatie.first][locatie.second]) { cuplaj--; }
                        else { blocat[locatie.first][locatie.second] = true; }
                    }
                }
            }
        }
    }
    
    cout << cuplaj;
    return 0;
}

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