Cod sursă (job #542441)

#include <bits/stdc++.h>

using namespace std;

const int dl[] = { -1, -1, 0, 0, 1, 1 };
const int dc[] = { 0, 1, -1, 1, -1, 0 };
//const int dl[] = { -1, -1, 0, 0, 1 };
//const int dc[] = { 0, 1, -1, 1, -1 };
const int nr_max = 500;
int v[2][nr_max * nr_max + 1];
char type[2][nr_max * nr_max + 1];
char apart[nr_max + 1][nr_max + 1];

int N, NN;

int find( int p, int x )
{
    if ( x != v[p][x] )
        return v[p][x] = find( p, v[p][x] );
    else
        return x;
}

int Union( int p, int x, int y )
{
    if ( rand() % 2 == 0 )
        v[p][x] = y;
    else
        v[p][y] = x;

    type[p][x] |= type[p][y];
    type[p][y] |= type[p][x];

    return ( type[p][x] == 3 );
}

void init()
{
    srand( time( NULL ) );

    memset( type, 0, sizeof( type ) );
    memset( apart, 0, sizeof( apart ) );

    for ( int i = 1; i <= N * N; ++i )
        v[0][i] = v[1][i] = i;

    for ( int i = 1; i <= N; ++i )
    {
        type[1][ ( i - 1 ) * N + 1 ] = 1;
        type[1][ ( i - 1 ) * N + N ] = 2;
    }

    for ( int i = 1; i <= N; ++i )
    {
        type[0][i] = 1;
        type[0][ ( N - 1 ) * N + i ] = 2;
    }
}

int valid( int p, int x, int y )
{
    return ( 1 <= x && x <= N && 1 <= y && y <= N && apart[x][y] == p + 1 );
}

int main()
{
    ifstream in("hex.in");
    ofstream out("hex.out");

    in >> N;

    init();

    for ( int i = 1; i <= N * N; ++i )
    {
        int a, b;

        in >> a >> b;

        apart[a][b] = ( i & 1 ) + 1;

        int stop = 0;

        for ( int k = 0; k < 6; ++k )
        {
            int x = a + dl[k];
            int y = b + dc[k];

            if ( valid( ( i & 1 ), x, y ) )
            {
                int fx = find( i & 1, N * ( x - 1 ) + y );
                int fy = find( i & 1, N * ( a - 1 ) + b );

                if ( fx != fy )
                {
                    stop |= Union( i & 1, fx, fy );
                }
            }
        }

        if ( stop )
        {
            out << i <<endl;
            i = N * N + 1;
        }
    }

    return 0;
}