Submission #1124516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124516		LucaIlie	Dango Maker (JOI18_dango_maker)	C++20	33 / 100	852 ms	307636 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

#include <bits/stdc++.h>

using namespace std;

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

    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 );
        perm.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;
                random_shuffle( adjL[u].begin(), adjL[u].end() );
                perm[u] = u;
            }
            random_shuffle( perm.begin(), perm.end() );
            for ( int i = 0; i < n; i++ ) {
                int u = perm[i];
                if ( pairL[u] == undef && findPair( u ) )
                    newMatch = true;
            }
        }

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

const int MAX_N = 3000;
char mat[MAX_N][MAX_N];
vector<int> vertices[MAX_N][MAX_N];

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 nrVerticesSide1 = 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' ) {
                vertices[l][c].push_back( nrVerticesSide1 );
                vertices[l][c + 1].push_back( nrVerticesSide1 );
                vertices[l][c + 2].push_back( nrVerticesSide1 );
                nrVerticesSide1++;
            }
        }
    }
    int nrVerticesSide2 = 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' ) {
                vertices[l][c].push_back( nrVerticesSide2 );
                vertices[l + 1][c].push_back( nrVerticesSide2 );
                vertices[l + 2][c].push_back( nrVerticesSide2 );
                nrVerticesSide2++;
            }
        }
    }
    cuplaj.init( nrVerticesSide1, nrVerticesSide2 );
    for ( int l = 0; l < n; l++ ) {
        for ( int c = 0; c < m; c++ ) {
            if ( vertices[l][c].size() == 2 )
                cuplaj.add_edge( vertices[l][c][0], vertices[l][c][1] );
        }
    }

    cuplaj.computeMaxMatching();
    cout << nrVerticesSide1 + nrVerticesSide2 - cuplaj.matching.size() << "\n";
}

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