Cod sursă (job #633925)

#include <stdio.h>
 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize ("unroll-loops")
 
static inline int min( const int& a, const int& b ) {
    return ( a <= b ? a : b );
}
 
static inline int max( const int& a, const int& b ) {
    return ( a >= b ? a : b );
}

#include <bitset>
#include <vector>
#include <stack>
#define MAX 500

int dl[] = { -1, -1, 0, 0, 1, 1 };
int dc[] = { 0, 1, 1, -1, 0, -1 };

struct Andrei {
    char type;
    std::bitset<MAX> bits;

    Andrei() {
        type = 3;
    }
} element;

std::vector<Andrei> el;
std::stack<int> st;
int pozitie[ MAX * MAX + 2 ];
bool a[ MAX + 1 ][ MAX + 1 ];
int dad[ MAX * MAX + 2 ];
int T, q, n;
int C[ 2 ];

int tata( int poz ) {
    if( dad[ poz ] == poz )
        return poz;
    return dad[ poz ] = tata( dad[ poz ] );
}

void reuniune( int V, int tata2 ) {
    int tata1 = V;
    el[ pozitie[ V ] ].bits |= el[ pozitie[ tata2 ] ].bits;
    if( el[ pozitie[ V ] ].bits.count() == n ) {
        FILE *fout = fopen( "hex.out", "w" );
        fprintf( fout, "%d\n", T );
        fclose( fout );
        exit( 0 );
    }
    st.push( pozitie[ tata2 ] );
    dad[ tata2 ] = V;
}

int main()
{
    FILE *fin = fopen( "hex.in", "r" );
    fscanf( fin, "%d", &n );
    q = n * n; 
    for( T = 1; T <= q; T++ ) {
        fscanf( fin, "%d %d", &C[ 1 ], &C[ 0 ] );
        int V = ( C[ 1 ] - 1 ) * n + C[ 0 ];
        a[ C[ 1 ] ][ C[ 0 ] ] = 1;
        dad[ V ] = V;
        int ind = T & 1;

        if( !st.empty() ) {
            pozitie[ V ] = st.top();
            st.pop();

            el[ pozitie[ V ] ].bits = 0;
            el[ pozitie[ V ] ].type = ind;
            el[ pozitie[ V ] ].bits[ C[ ind ] ] = 1;
        } else {
            pozitie[ V ] = el.size();

            element.bits = 0;
            element.type = ind;
            element.bits[ C[ ind ] ] = 1;
            el.push_back( element );
        }

        int pp;
        for( int d = 0; d < 6; d++ ) {
            int l = C[ 1 ] + dl[ d ];
            int c = C[ 0 ] + dc[ d ];
            if( l > 0 && c > 0 && l <= n && c <= n && a[ l ][ c ] ) {
                int val = ( l - 1 ) * n + c;
                if( el[ pozitie[ ( pp = tata( val ) ) ] ].type == ind )
                    reuniune( V, pp );
            }
        }   
    }
    
    fclose( fin );
    return 0;
}