Submission #357629

#	Time	Username	Problem	Language	Result	Execution time	Memory
357629		cute_hater	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	464 ms	262148 KiB

dango_maker

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <algorithm>
#include <string>
#include <cmath>
#include <cstdio>
#include <iomanip>
#include <fstream>
#include <cassert>
#include <cstring>
#include <numeric>
#include <ctime>
#include <complex>
#include <bitset>
#include <random>
#include <climits>
#include <stack>


/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,sse4.1,sse4.2,popcnt,abm,mmx,avx,avx2,tune=native")*/

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int ll
#define double ld
#define loop(i, n) for(int i = 0; i < (int)n; ++i)
#define loop1(i, n) for(int i = 1; i <= (int)n; ++i)
#define F first
#define S second
#define pb push_back
#define pi pair <int, int>
#define all(x) begin(x), end(x)
#define ti tuple <int, int, int>
#define Point Vect
#define no {cout << -1; return;}
#define yes {cout << "Yes"; return;}
#define mkp make_pair
#define mkt make_tuple
#define cerr if(0) cerr

const int N = 3007;

short f[N][N];
bool usedl[N * N], usedr[N * N];
int g[3][N * N], sz[N * N], used[N * N], mtr[N * N], mtl[N * N];

bool kun(int v, int c) {
    used[v] = c;
    for (int i = 0; i < 3 && g[i][v] != -1; ++i) {
        int u = g[i][v];
        if (mtr[u] == -1 || used[mtr[u]] != c && kun(mtr[u], c)) {
            mtr[u] = v;
            return true;
        }
    }
    return false;
}

void dfs(int v) {
    if (v == -1 || usedl[v])
        return;
    usedl[v] = 1;
    for (int i = 0; i < 3 && g[i][v] != -1; ++i) {
        int u = g[i][v];
        if (mtl[v] == u)
            continue;
        if (!usedr[u]) {
            usedr[u] = 1;
            dfs(mtr[u]);
        }
    }
}

void solve() {
    loop(i, N * N) {
        mtr[i] = mtl[i] = g[0][i] = g[1][i] = g[2][i] = -1;
    }
    int n, m;
    cin >> n >> m;
    for (int i = 2; i <= n + 1; ++i) {
        for (int j = 2; j <= m + 1; ++j) {
            char c; cin >> c;
            f[i][j] = (c == 'R' ? 1 : (c == 'G' ? 2 : 3));
        }
    }
    for (int i = 2; i <= n + 1; ++i) {
        for (int j = 2; j <= m + 1; ++j) {
            if (f[i][j] == 1 && f[i][j + 1] == 2 && f[i][j + 2] == 3) {
                int v = (i - 2) * m + (j - 2);
                if (f[i + 1][j] == 2 && f[i + 2][j] == 3)
                    g[sz[v]++][v] = (i - 2) * m + (j - 2);
                if (f[i - 1][j + 1] == 1 && f[i + 1][j + 1] == 3)
                    g[sz[v]++][v] = (i - 3) * m + (j - 1);
                if (f[i - 2][j + 2] == 1 && f[i - 1][j + 2] == 2)
                    g[sz[v]++][v] = (i - 4) * m + j;
            }
        }
    }
    int cnt = 0;
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            kun((i - 2) * m + (j - 2), ++cnt);
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            if (mtr[(i - 2) * m + (j - 2)] != -1)
                mtl[mtr[(i - 2) * m + (j - 2)]] = (i - 2) * m + (j - 2);
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            if (mtl[(i - 2) * m + (j - 2)] == -1)
                dfs((i - 2) * m + (j - 2));
    int ans = 0;
    for (int i = 2; i <= n + 1; ++i)
        for (int j = 2; j <= m + 1; ++j)
            ans += (f[i][j] == 1 && f[i][j + 1] == 2 && f[i][j + 2] == 3 && usedl[(i - 2) * m + (j - 2)]) + (f[i][j] == 1 && f[i + 1][j] == 2 && f[i + 2][j] == 3 && !usedr[(i - 2) * m + (j - 2)]);
    cout << ans;
}

signed main() {
    //freopen("b2.txt", "r", stdin);
    //freopen("ans9.txt", "w", stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    //int t; cin >> t; loop(i, t)
    solve();
    return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'bool kun(int, int)':
dango_maker.cpp:62:47: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   62 |         if (mtr[u] == -1 || used[mtr[u]] != c && kun(mtr[u], c)) {
      |                             ~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~

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