Cod sursă (job #634402)

#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 502
 
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;

    //for( int i = 1; i <= n; i++ )
     //   printf( "%d", (int)el[ pozitie[ V ] ].bits[ i ] );
   // printf( "\n" );
  //  for( int i = 1; i <= n; i++ )
  //      printf( "%d", (int)el[ pozitie[ tata2 ] ].bits[ i ] );
   // printf( "\n" );
    el[ pozitie[ V ] ].bits |= el[ pozitie[ tata2 ] ].bits;

   // for( int i = 1; i <= n; i++ )
  //      printf( "%d", (int)el[ pozitie[ V ] ].bits[ i ] );
  //  printf( "\n\n\n" );
//

    st.push( pozitie[ tata2 ] );
    dad[ tata2 ] = dad[ tata1 ] = 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[ 0 ], &C[ 1 ] );
        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 ) {
                   // printf( "%d %d <- %d %d  `%d`\n", l, c, C[ 1 ], C[ 0 ], ind );
                    reuniune( V, pp );
                }
            }
        }   

        if( el[ pozitie[ tata( V ) ] ].bits.count() == n ) {
           // printf( "->\n" );
            FILE *fout = fopen( "hex.out", "w" );
            fprintf( fout, "%d\n", T );
            fclose( fout );
            exit( 0 );
        }
    }
    
    fclose( fin );
    return 0;
}