Submission #1677873

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <algorithm>
#define repu(i,x,y) for (int i=x; i<=y; ++i)
#define mid ((l+r)>>1)
using namespace std;

int n,tot,p[20100],id[20][20100],log_[20100],dfn[400100],low[400100],stk[400100],top,scc[400100],clk;
struct data
{
    int x,id;
    bool operator<(const data &t) const
    {
        return x<t.x;
    }
} a[20100];
struct edge
{
    int u,v;
    edge *nxt;
} pool[1000000],*tp=pool,*fst[400100],*bnd;

void addedge(int u,int v)
{
    *tp=(edge){u,v,fst[u]},fst[u]=tp++;
}

void add(int x,int l,int r)
{
    if (l>r)
        return;
    int t=p[x>n?x-n:x+n];
    if (l<=t && r>=t)
    {
        add(x,l,t-1),add(x,t+1,r);
        return;
    }
    t=log_[r-l+1];
    addedge(x,id[t][l]),addedge(x,id[t][r-(1<<t)+1]);
}

void dfs(int x)
{
    dfn[x]=low[x]=++clk,stk[++top]=x;
    for (edge *i=fst[x]; i; i=i->nxt)
    {
        if (!dfn[i->v])
            dfs(i->v);
        if (!scc[i->v])
            low[x]=min(low[x],low[i->v]);
    }
    if (dfn[x]==low[x])
        for (; stk[top+1]!=x; scc[stk[top--]]=x);
}

bool solve(int d)
{
    for (; tp>bnd; --tp,fst[tp->u]=tp->nxt);
    for (int i=1,l=1,r=1; i<=n*2; ++i)
    {
        for (; a[i].x-a[l].x>=d; ++l);
        for (; r<n*2 && a[r+1].x-a[i].x<d; ++r);
        add(a[i].id,l,i-1),add(a[i].id,i+1,r);
    }
    memset(dfn,0,sizeof(dfn));
    memset(scc,0,sizeof(scc));
    repu(i,1,tot)
        if (!dfn[i])
            dfs(i);
    repu(i,1,n)
        if (scc[i]==scc[i+n])
            return 0;
    return 1;
}

int main()
{
    scanf("%d",&n);
    repu(i,1,n)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        a[i]=(data){x,i},a[i+n]=(data){y,i+n};
    }
    sort(a+1,a+1+n*2);
    repu(i,1,n*2)
        p[a[i].id]=i,id[0][i]=a[i].id>n?a[i].id-n:a[i].id+n;
    repu(i,2,n*2)
        log_[i]=log_[i>>1]+1;
    tot=n*2;
    repu(i,1,log_[n*2])
        repu(j,1,n*2-(1<<i)+1)
        {
            id[i][j]=++tot;
            addedge(id[i][j],id[i-1][j]);
            addedge(id[i][j],id[i-1][j+(1<<i-1)]);
        }
    bnd=tp;
    int l=1,r=1e9;
    while (l<r)
        solve(mid)?l=mid+1:r=mid;
    printf("%d\n",l-1);
    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:78:19: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
./Main.cpp:82:28: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d",&x,&y);
                            ^

Judge Result