Cod sursă (job #80772)

#include <cstdio>

using namespace std;

#define MAX 251001

int m[502][502],k,ind;

struct mutari{
    int p;
    int x;
    int y;
}v[MAX+1];

void init(int n)
{
    int j;

    for(j=1;j<=n;j++)
    {
        v[k].p=1;
        v[k].x=0;
        v[k].y=j;
        k++;
    }

    for(j=1;j<=n;j++)
    {
        v[k].p=2;
        v[k].x=n+1;
        v[k].y=j;
        k++;
    }

    for(j=1;j<=n;j++)
    {
        v[k].p=3;
        v[k].x=j;
        v[k].y=0;
        k++;
    }

    for(j=1;j<=n;j++)
    {
        v[k].p=4;
        v[k].x=j;
        v[k].y=n+1;
        k++;
    }

    int nr=5;
    ind=k;
    for(j=0;j<n*n;j++)
    {
        v[k].p=nr++;
        k++;
    }


}

int find(int x)
{
    int r=x;
    while(v[r].p!=r)
        r=v[r].p;
    while(v[x].p!=r)
    {
        int tmp=v[x].p;
        v[x].p=r;
        x=tmp;
    }
    return r;
}

void union1 (int x,int y)
{
    int rx=find(x), ry=find(y);
    if(rx!=ry)
        v[rx].p=ry;
}

int main()
{
    FILE *fin,*fout;

    fin=fopen("hex.in","r");
    fout=fopen("hex.out","w");

    int n,i,j,a,b,indstr=0,indsta=0,indjosr=0,indjosa=0;

    fscanf(fin,"%d",&n);

    init(n);
    for(i=0;i<=n;i++)
    {
        m[0][i]=2;
        m[n+1][i]=4;
        m[i][0]=1;
        m[n+1][0]=3;
    }

    for(i=1;i<=n;i++)
    {
        fscanf(fin,"%d%d",&v[ind+i-1].x,&v[ind+i-1].y);
        m[v[ind+i-1].x][v[ind+i-1].y]=ind;

        a=v[ind+i-1].x;
        b=v[ind+i-1].y;

        ind++;
        bool r=m[a][b]%2;

        if(r==m[a+1][b]%2 && m[a+1][b]!=0)
            union1(m[a][b],m[a+1][b]);

        if(r==m[a-1][b]%2 && m[a-1][b]!=0)
            union1(m[a][b],m[a-1][b]);

        if(r==m[a][b+1]%2 && m[a][b+1]!=0)
            union1(m[a][b],m[a][b+1]);

        if(r==m[a][b-1]%2 && m[a][b-1]!=0)
            union1(m[a][b],m[a][b-1]);

        if(r==m[a+1][b-1]%2 && m[a+1][b-1]!=0)
            union1(m[a][b],m[a+1][b-1]);

        if(r==m[a-1][b+1]%2 && m[a-1][b+1]!=0)
            union1(m[a][b],m[a-1][b+1]);

        if(find(0)==find(n) || find(2*n)==find(3*n))
        {
            fprintf(fout,"%d",i);
            break;
        }

    }

    return 0;
}