Cod sursă (job #542206)

#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 Nmax = 500;
int f[Nmax * Nmax + 1];
int aux[Nmax * Nmax + 1];
short w[Nmax * Nmax + 1];
char q[Nmax + 2][Nmax + 2];
int N, NN;


int cauta( int x )
{
    int r = x;
    while ( f[r] != r )
        r = f[r];
    return r;
}

int check( int x, int y )
{
    if ( aux[x] > aux[y] )
        f[y] = x;
    else
        f[x] = y;
    if ( aux[x] == aux[y] )
        aux[y]++;
    if ( !w[x] )
        w[x] = w[y];
    if ( !w[y] )
        w[y] = w[x];
    if ( ( w[x] | w[y] ) == 9 || ( w[x] | w[y] ) == 6 )
        return 1;
    else
        return 0;
}

void init()
{
    NN = N * N;
    for ( int i = 1; i <= NN; ++i )
    {
        f[i] = i;
        aux[i] = 1;
        w[i] = 0;
    }
    for ( int i = 0; i <= N + 1; ++i )
        for ( int j = 0; j <= N + 1; ++j )
            q[i][j] = 0;

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


int main()
{
    ifstream cin("hex.in");
    ofstream cout("hex.out");
    cin >> N;
    init();
    for ( int i = 1, a, b; i <= NN; ++i )
    {
        cin >> a >> b;
        q[a][b] = 1 + ( i & 1 );
        int stop = 0;
        for ( int k = 0; k < 6 && !stop; ++k )
        {
            int x = a + dl[k];
            int y = b + dc[k];
            if ( q[a][b] == q[x][y] )
            {
                int fab = cauta( N * ( a - 1 ) + b );
                int fxy = cauta( N * ( x - 1 ) + y );
                if ( fab != fxy )
                    stop = check( fab, fxy );
            }
        }
        if ( stop )
        {
            cout << i << "\n";
            i = NN + 1;
        }
    }
    return 0;
}