Submission #1124521

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124521		LucaIlie	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	821 ms	327680 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

struct BIPARTITE_MATCHING {
    const int undef = -1;
    int n, m, matchingSize;
    vector<bool> vis;
    vector<int> pairL, pairR;
    vector<vector<int>> adjL, adjR;

    void init( int _n, int _m ) {
        n = _n;
        m = _m;
        pairL.resize( n );
        for ( int u = 0; u < n; u++ )
            pairL[u] = undef;
        pairR.resize( m );
        for ( int v = 0; v < m; v++ )
            pairR[v] = undef;
        adjL.resize( n );
        adjR.resize( m );
        vis.resize( n );
    }

    void add_edge( int u, int v ) {
        adjL[u].push_back( v );
        adjR[v].push_back( u );
    }

    bool findPair( int u ) {
        if ( vis[u] )
            return false;

        vis[u] = true;
        for ( int v: adjL[u] ) {
            if ( pairR[v] == undef || findPair( pairR[v] ) ) {
                pairL[u] = v;
                pairR[v] = u;
                return true;
            }
        }
        return false;
    }

    void computeMaxMatching() {
        bool newMatch = true;

        while ( newMatch ) {
            newMatch = false;
            for ( int u = 0; u < n; u++ )
                vis[u] = false;
            for ( int i = 0; i < n; i++ ) {
                int u = i;
                if ( pairL[u] == undef && findPair( u ) )
                    newMatch = true;
            }
        }

        matchingSize = 0;
        for ( int u = 0; u < n; u++ ) {
            if ( pairL[u] != undef )
                matchingSize++;
        }
    }
} cuplaj;

const int MAX_N = 3000;
char mat[MAX_N][MAX_N];
int vertices[MAX_N][MAX_N][2];

int main() {
    int n, m;

    cin >> n >> m;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ )
            cin >> mat[l][c];
    }

    int nrVerticesSide0 = 0;
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m - 2; c++ ) {
            if ( mat[l][c] == 'R' && mat[l][c + 1] == 'G' && mat[l][c + 2] == 'W' ) {
                nrVerticesSide0++;
                vertices[l][c][0] = nrVerticesSide0;
                vertices[l][c + 1][0] = nrVerticesSide0;
                vertices[l][c + 2][0] = nrVerticesSide0;
            }
        }
    }
    int nrVerticesSide1 = 0;
    for ( int l = 0; l < n - 2; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( mat[l][c] == 'R' && mat[l + 1][c] == 'G' && mat[l + 2][c] == 'W' ) {
                nrVerticesSide1++;
                vertices[l][c][1] = nrVerticesSide1;
                vertices[l + 1][c][1] = nrVerticesSide1;
                vertices[l + 2][c][1] = nrVerticesSide1;
            }
        }
    }
    cuplaj.init( nrVerticesSide0 + 1, nrVerticesSide1 + 1 );
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( vertices[l][c][0] != 0 && vertices[l][c][1] != 0 )
                cuplaj.add_edge( vertices[l][c][0], vertices[l][c][1] );
        }
    }

    cuplaj.computeMaxMatching();
    cout << nrVerticesSide0 + nrVerticesSide1 - cuplaj.matchingSize << "\n";
}

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