Cod sursă (job #755451)

#include <bits/stdc++.h>
#include <ctime>
using namespace std;

#define MOD 1000000007
#define NMAX 250000
ifstream fin("hex.in");
ofstream fout("hex.out");
int dx[7]={0,-1,-1,0,0,1,1};
int dy[7]={0,0,1,-1,1,-1,0};
int n;
int parent[NMAX+1];
short msk[NMAX+1];

bool in(int x,int y)
{
    return x>=1 && x<=n && y>=1 && y<=n;
}
int root(int x)
{
    if(x==parent[x])
    {
        return x;
    }
    return parent[x]=root(parent[x]);
}
void unite(int x,int y)
{
    x=root(x),y=root(y);
    if(rand()%2)
    {
        swap(x,y);
    }
    parent[y]=x;
    msk[x]|=msk[y];

}
bool ok(int x)
{
    x=root(x);
    if(msk[x] & (1<<0))
    {
        return (msk[x] & (1<<2)) && (msk[x] & (1<<4));
    }
    else if(msk[x] & (1<<1))
    {
        return (msk[x] & (1<<3)) && (msk[x] & (1<<5));
    }
    return 0;
}
bool ap(int x,int y)
{
    x=msk[x],y=msk[y];
    if(x & (1<<0))
    {
        return (y & (1<<0));
    }
    return y&(1<<1);
}
int main()
{
    fin >> n;

    int res=0;
    for(int k=1;k<=n*n && !res;k++)
    {
        int x,y;
        fin >> x >> y;
        int a=(x-1)*n+y;
        parent[a]=a;
        msk[a]=1<<(k%2);

        for(int i=1;i<=6;i++)
        {
            int x1=dx[i]+x,y1=dy[i]+y;
            int b=(x1-1)*n+y1;
            if(x1==0)
            {
                msk[a]|=1<<2;
            }
            if(y1==n+1)
            {
                msk[a]|=1<<3;
            }
            if(x1==n+1)
            {
                msk[a]|=1<<4;
            }
            if(y1==0)
            {
                msk[a]|=1<<5;
            }
            if(!in(x1,y1) || !ap(a,b))
            {
                continue;
            }
            unite(a,b);
            if(ok(a) || ok(b))
            {
                res=k;
            }
        }
        if(ok(a))
        {
            res=k;
        }
    }
    fout << res;


}