Cod sursă (job #399130)

#include <fstream>

using namespace std;
ifstream f("hex.in");
ofstream g("hex.out");
int n,x,i,j,v[502][502],d[502][502],d2[502][502],nr,l,c,r2;
int p[500*500+10],finalst[500*500+10],finaldr[500*500+10],h[500*500+10];
int find(int x)
{
    int r=x;
    while(p[r]!=r)
    {
        r=p[r];
        finalst[p[r]]=max(finalst[r],finalst[p[r]]);
        finaldr[p[r]]=max(finaldr[r],finaldr[p[r]]);
        finalst[r]=max(finalst[r],finalst[p[r]]);
        finaldr[r]=max(finaldr[r],finaldr[p[r]]);
    }
    while(p[x]!=r)
    {
        int tmp=p[x];
        p[x]=r;
        x=tmp;
        finalst[x]=max(finalst[x],finalst[tmp]);
        finaldr[x]=max(finaldr[x],finaldr[tmp]);
        finalst[tmp]=max(finalst[x],finalst[tmp]);
        finaldr[tmp]=max(finaldr[x],finaldr[tmp]);
    }
    return r;
}
void union1(int x,int y)
{
    int rx=find(x);
    int ry=find(y);
    finalst[rx]=max(finalst[ry],finalst[rx]);
    finaldr[rx]=max(finaldr[ry],finaldr[rx]);
    if (rx!=ry)
    {
        if(h[rx]<h[ry])
        {
            p[rx]=ry;
            finalst[p[rx]]=max(finalst[rx],finalst[p[rx]]);
            finaldr[p[rx]]=max(finaldr[rx],finaldr[p[rx]]);
            finalst[rx]=max(finalst[rx],finalst[p[rx]]);
            finaldr[rx]=max(finaldr[rx],finaldr[p[rx]]);
        }
        else if(h[rx]>h[ry])
        {
            p[ry]=rx;
            finalst[p[ry]]=max(finalst[ry],finalst[p[ry]]);
            finaldr[p[ry]]=max(finaldr[ry],finaldr[p[ry]]);
            finalst[ry]=max(finalst[ry],finalst[p[ry]]);
            finaldr[ry]=max(finaldr[ry],finaldr[p[ry]]);
        }
        else
        {
            p[rx]=ry;
            h[ry]++;
            finalst[p[rx]]=max(finalst[rx],finalst[p[rx]]);
            finaldr[p[rx]]=max(finaldr[rx],finaldr[p[rx]]);
            finalst[rx]=max(finalst[rx],finalst[p[rx]]);
            finaldr[rx]=max(finaldr[rx],finaldr[p[rx]]);
        }
    }
}
int main()
{
    f>>n;
    x=n*n;
    for(i=1; i<=n; i++)
    {
        for(j=1; j<=n; j++)
        {
            v[i][j]=++nr;
            p[nr]=nr;
        }
    }
    while(x--)
    {
        f>>l>>c;
        if(r2==0)
        {
            r2=1;
            h[v[l][c]]=1;
            d[l][c]=1;
            if(c==1)
            {
                finalst[v[l][c]]=1;
            }
            if(c==n)
            {
                finaldr[v[l][c]]=1;
            }
            if(d[l][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
                finalst[v[l][c-1]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c-1]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
            }
            if(d[l][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
                finalst[v[l][c+1]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c+1]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
            }
            if(d[l-1][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
                finalst[v[l-1][c+1]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l-1][c+1]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
            }
            if(d[l-1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
                finalst[v[l-1][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l-1][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
            }
            if(d[l+1][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
                finalst[v[l+1][c-1]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l+1][c-1]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
            }
            if(d[l+1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
                finalst[v[l+1][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l+1][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
            }
            if(d[l][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
                finalst[v[l][c-1]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c-1]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
                union1(v[l][c-1],v[l][c]);
            }
            if(d[l][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
                finalst[v[l][c+1]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c+1]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
                union1(v[l][c+1],v[l][c]);
            }
            if(d[l-1][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
                finalst[v[l-1][c+1]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l-1][c+1]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
                union1(v[l-1][c+1],v[l][c]);
            }
            if(d[l-1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
                finalst[v[l-1][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l-1][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
                union1(v[l-1][c],v[l][c]);
            }
            if(d[l+1][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
                finalst[v[l+1][c-1]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l+1][c-1]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
                union1(v[l+1][c-1],v[l][c]);
            }
            if(d[l+1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
                finalst[v[l+1][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l+1][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
                union1(v[l+1][c],v[l][c]);
            }
            if(finaldr[v[l][c]]==1 && finalst[v[l][c]]==1)
            {
                g<<n*n-x<<'\n';
                break;
            }
        }
        else if(r2==1)
        {
            r2=0;
            h[v[l][c]]=1;
            d2[l][c]=1;
            if(l==1)
            {
                finalst[v[l][c]]=1;
            }
            if(l==n)
            {
                finaldr[v[l][c]]=1;
            }
            if(d2[l][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
                finalst[v[l][c-1]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c-1]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
            }
            if(d2[l][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
                finalst[v[l][c+1]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c+1]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
            }
            if(d2[l-1][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
                finalst[v[l-1][c+1]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l-1][c+1]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
            }
            if(d2[l-1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
                finalst[v[l-1][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l-1][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
            }
            if(d2[l+1][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
                finalst[v[l+1][c-1]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l+1][c-1]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
            }
            if(d2[l+1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
                finalst[v[l+1][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l+1][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
            }
            if(d2[l][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
                finalst[v[l][c-1]]=max(finalst[v[l][c]],finalst[v[l][c-1]]);
                finaldr[v[l][c-1]]=max(finaldr[v[l][c]],finaldr[v[l][c-1]]);
                union1(v[l][c-1],v[l][c]);
            }
            if(d2[l][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
                finalst[v[l][c+1]]=max(finalst[v[l][c]],finalst[v[l][c+1]]);
                finaldr[v[l][c+1]]=max(finaldr[v[l][c]],finaldr[v[l][c+1]]);
                union1(v[l][c+1],v[l][c]);
            }
            if(d2[l-1][c+1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
                finalst[v[l-1][c+1]]=max(finalst[v[l][c]],finalst[v[l-1][c+1]]);
                finaldr[v[l-1][c+1]]=max(finaldr[v[l][c]],finaldr[v[l-1][c+1]]);
                union1(v[l-1][c+1],v[l][c]);
            }
            if(d2[l-1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
                finalst[v[l-1][c]]=max(finalst[v[l][c]],finalst[v[l-1][c]]);
                finaldr[v[l-1][c]]=max(finaldr[v[l][c]],finaldr[v[l-1][c]]);
                union1(v[l-1][c],v[l][c]);
            }
            if(d2[l+1][c-1]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
                finalst[v[l+1][c-1]]=max(finalst[v[l][c]],finalst[v[l+1][c-1]]);
                finaldr[v[l+1][c-1]]=max(finaldr[v[l][c]],finaldr[v[l+1][c-1]]);
                union1(v[l+1][c-1],v[l][c]);
            }
            if(d2[l+1][c]!=0)
            {
                finalst[v[l][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
                finalst[v[l+1][c]]=max(finalst[v[l][c]],finalst[v[l+1][c]]);
                finaldr[v[l+1][c]]=max(finaldr[v[l][c]],finaldr[v[l+1][c]]);
                union1(v[l+1][c],v[l][c]);
            }
            if(finaldr[v[l][c]]==1 && finalst[v[l][c]]==1)
            {
                g<<n*n-x<<'\n';
                break;
            }
        }
    }
    n=0;
    return 0;
}