Submission #369126

#	Time	Username	Problem	Language	Result	Execution time	Memory
369126		Lam_lai_cuoc_doi	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	445 ms	262148 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;

const bool typetest = 0;
const int N = 3e3 + 5;
struct HopCroft_Karp
{
    const int NoMatch = -1;
    const int Inf = 1e9 + 7;
    int nx, ny;
    bool found;
    vector<int> match, S, h;
    vector<vector<int>> adj;
    HopCroft_Karp(int nx, int ny)
    {
        this->nx = nx;
        this->ny = ny;
        adj.resize(nx + 1);
        match.resize(ny + 1, NoMatch);
        h.resize(ny + 1, Inf);
        S.reserve(nx);
        for (int i = 1; i <= nx; ++i)
            S.push_back(i);
    }
    void AddEdge(int x, int y)
    {
        adj[x].push_back(y);
    }
    bool BFS()
    {
        queue<int> q;
        fill(h.begin(), h.end(), 0);
        for (auto i : S)
            for (auto j : adj[i])
                if (h[j] == 0)
                {
                    h[j] = 1;
                    q.push(j);
                }
        while (q.size())
        {
            int c = q.front();
            q.pop();
            int x;
            if ((x = match[c]) == NoMatch)
                return true;
            for (auto i : adj[x])
                if (h[i] == 0)
                {
                    h[i] = h[c] + 1;
                    q.push(i);
                }
        }
        return false;
    }
    void dfs(int x, int lv)
    {
        for (auto i : adj[x])
            if (h[i] == lv + 1)
            {
                if (match[i] != -1)
                    dfs(match[i], lv + 1);
                else
                    found = 1;
                if (found)
                {
                    match[i] = x;
                    return;
                }
            }
    }
    int MaxMatch()
    {
        int ans(0);
        while (BFS())
        {
            for (int i = S.size() - 1; ~i; --i)
            {
                found = 0;
                dfs(S[i], 0);
                if (found)
                {
                    S[i] = S.back();
                    S.pop_back();
                    ++ans;
                }
            }
        }
        return ans;
    }
};
const ll Inf = 1e17;
int n, m, nx, ny;
int row[N][N], col[N][N];
string s[N];

void Read()
{
    cin >> m >> n;
    for (int i = 1; i <= m; ++i)
    {
        cin >> s[i];
        s[i] = " " + s[i];
    }
}

void Solve()
{
    memset(row, -1, sizeof row);
    memset(col, -1, sizeof col);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n - 2; ++j)
            if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W')
                row[i][j] = ++nx;
    for (int i = 1; i <= m - 2; ++i)
        for (int j = 1; j <= n; ++j)
            if (s[i][j] == 'R' && s[i + 1][j] == 'G' && s[i + 2][j] == 'W')
                col[i][j] = ++ny;
    HopCroft_Karp match(nx, ny);
    for (int i = 1; i <= m; ++i)
        for (int j = 1; j <= n; ++j)
            if (row[i][j] != -1)
            {
                if (col[i][j] != -1)
                    match.AddEdge(row[i][j], col[i][j]);
                if (i > 1 && col[i - 1][j + 1] != -1)
                    match.AddEdge(row[i][j], col[i - 1][j + 1]);
                if (i > 2 && col[i - 2][j + 2] != -1)
                    match.AddEdge(row[i][j], col[i - 2][j + 2]);
            }
    cout << (nx + ny - match.MaxMatch());
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t(1);
    if (typetest)
        cin >> t;
    for (int _ = 1; _ <= t; ++_)
    {
        Read();
        Solve();
    }
}

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