Submission #1124529

#	Time	Username	Problem	Language	Result	Execution time	Memory
1124529		LucaIlie	Dango Maker (JOI18_dango_maker)	C++20	0 / 100	62 ms	70764 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

const int MAX_VERT = 3e6;

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

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

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

    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 vertices0[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 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++;
                vertices0[l][c] = nrVerticesSide0;
                vertices0[l][c + 1] = nrVerticesSide0;
                vertices0[l][c + 2] = 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++;
            }
        }
    }
    cuplaj.init( nrVerticesSide0 + 1, nrVerticesSide1 + 1 );
    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++;
                if ( vertices0[l][c] != 0 )
                    cuplaj.add_edge( vertices0[l][c], nrVerticesSide1 );
                if ( vertices0[l + 1][c] != 0 )
                    cuplaj.add_edge( vertices0[l + 1][c], nrVerticesSide1 );
                if ( vertices0[l + 2][c] != 0 )
                    cuplaj.add_edge( vertices0[l + 2][c], nrVerticesSide1 );
            }
        }
    }

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

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