Submission #202204

#	Time	Username	Problem	Language	Result	Execution time	Memory
202204		tri	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	160 ms	220664 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int, int> pi;
typedef pair<ll, ll> pl;

typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<ll> vl;

#define pb push_back
#define f first
#define s second

namespace debug {
    const int DEBUG = true;

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x);

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x);

    template<class T>
    void pr(const vector<T> &x);

    template<class T>
    void pr(const set<T> &x);

    template<class T1, class T2>
    void pr(const map<T1, T2> &x);

    template<class T>
    void pr(const T &x) { if (DEBUG) cout << x; }

    template<class T, class... Ts>
    void pr(const T &first, const Ts &... rest) { pr(first), pr(rest...); }

    template<class T1, class T2>
    void pr(const pair<T1, T2> &x) { pr("{", x.f, ", ", x.s, "}"); }

    template<class T>
    void prIn(const T &x) {
        pr("{");
        bool fst = 1;
        for (auto &a : x) {
            pr(fst ? "" : ", ", a), fst = 0;
        }
        pr("}");
    }

    template<class T, size_t SZ>
    void pr(const array<T, SZ> &x) { prIn(x); }

    template<class T>
    void pr(const vector<T> &x) { prIn(x); }

    template<class T>
    void pr(const set<T> &x) { prIn(x); }

    template<class T1, class T2>
    void pr(const map<T1, T2> &x) { prIn(x); }

    void ps() { pr("\n"), cout << flush; }

    template<class Arg, class... Args>
    void ps(const Arg &first, const Args &... rest) {
        pr(first, " ");
        ps(rest...);
    }
}
using namespace debug;


const int MAXN = 9e6 + 10;

vi aL[MAXN];

bool act[MAXN];

int N, M;

int lin(int i, int j, int t) {
    return N * M * t + i * M + j;
}

string g[3010];

bool checkV(int i, int j) {
    if (j < 0 || M <= j) return false;
    if (i < 0 || i + 2 >= N) return false;

    return g[i][j] == 'R' && g[i + 1][j] == 'G' && g[i + 2][j] == 'W';
}


bool checkH(int i, int j) {
    if (i < 0 || N <= i) return false;
    if (j < 0 || j + 2 >= M) return false;

    return g[i][j] == 'R' && g[i][j + 1] == 'G' && g[i][j + 2] == 'W';
}

int cnt0, cnt1;

void dfs(int x) {
//    ps(x);
    act[x] = false;

    if (x < N * M) {
        cnt0++;
    } else {
        cnt1++;
    }

    for (int aV : aL[x]) {
        if (act[aV]) {
            dfs(aV);
        }
    }
}

int main() {
    cin >> N >> M;

    for (int i = 0; i < N; i++) {
        cin >> g[i];
    }

    fill(act, act + MAXN, false);

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
//            ps(i, j);
            if (checkV(i, j)) {
                int cCell = lin(i, j, 0);
                act[cCell] = true;


                for (int d = 0; d <= 2; d++) {
                    if (checkH(i + d, j - d)) {
                        int aCell = lin(i + d, j - d, 1);
                        aL[cCell].pb(aCell);
                    }
                }
            }
            if (checkH(i, j)) {
                int cCell = lin(i, j, 1);
                act[cCell] = true;

                for (int d = 0; d <= 2; d++) {
                    if (checkV(i - d, j + d)) {
                        int aCell = lin(i - d, j + d, 0);
                        aL[cCell].pb(aCell);
                    }
                }
            }
        }
    }

//    ps("hello");

    int sum = 0;
    for (int x = 0; x < 2 * N * M; x++) {
        if (act[x]) {
            cnt0 = 0, cnt1 = 0;
            dfs(x);
            sum += max(cnt0, cnt1);
        }
    }
    cout << sum << endl;
}

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