Submission #1867805

---

Source Code Expand

#include <algorithm>
#include <cstring>
#include <cstdio>
const int N=10005;
int a[N],b[N],c[N*4],low[N*4],dfn[N*4],stack[N*4],ls[N*4],rs[N*4],
	id[N*2],fst[N*4],n,m,nodes,tot,cnt,col,top;
bool u[N*4];
struct P{int x,id;}q[N*2];
bool cmp(P a,P b){
	return a.x<b.x;
}
struct Edge{int to,nxt;}e[N*120];
void addedge(int x,int y){
	e[++tot].to=y;e[tot].nxt=fst[x];fst[x]=tot;
}
void build(int now,int l,int r){
	if (l==r){
		id[l]=now;
		return;
	}
	int mid=(l+r)>>1;
	build(ls[now]=++nodes,l,mid);
	build(rs[now]=++nodes,mid+1,r);
}
void add(int now,int l,int r,int x,int y,int z){
	if (x<=l && r<=y){
		addedge(z,now);
		return;
	}
	int mid=(l+r)>>1;
	if (x<=mid) add(ls[now],l,mid,x,y,z);
	if (y>mid) add(rs[now],mid+1,r,x,y,z);
}
void tarjan(int x){
	dfn[x]=low[x]=++cnt;
	u[stack[++top]=x]=1;
	for (int i=fst[x];i;i=e[i].nxt){
		int y=e[i].to;
		if (!dfn[y]){
			tarjan(y);
			low[x]=std::min(low[x],low[y]);
		}
		else if (u[y]) low[x]=std::min(low[x],dfn[y]);
	}
	if (low[x]==dfn[x]){
		++col;
		for (;stack[top]!=x;u[stack[top--]]=0) c[stack[top]]=col;
		c[x]=col;u[x]=0;top--;
	}
}
bool check(int mid){
	memset(fst,0,sizeof fst);
	tot=0;
	for (int i=1;i<=nodes;i++)
		if (ls[i]) addedge(i,ls[i]),addedge(i,rs[i]);
	for (int i=1,l=1,r=1;i<=m;i++){
		for (;q[l].x<=q[i].x-mid;l++);
		for (;r<m && q[r+1].x<q[i].x+mid;r++);
		if (l<i) add(1,1,m,l,i-1,id[q[i].id]);
		if (i<r) add(1,1,m,i+1,r,id[q[i].id]);
	}
	memset(dfn,0,sizeof dfn);
	memset(u,0,sizeof u);
	cnt=col=top=0;
	for (int i=1;i<=nodes;i++)
		if (!dfn[i]) tarjan(i);
	for (int i=1;i<=n;i++)
		if (c[id[a[i]]]==c[id[b[i]]]) return 0;
	return 1;
}
int main(){
	scanf("%d\n",&n);m=n*2;
	for (int i=1;i<=n;i++){
		scanf("%d%d",&q[i*2-1].x,&q[i*2].x);
		q[i*2-1].id=q[i*2].id=i;
	}
	std::sort(q+1,q+m+1,cmp);
	for (int i=1;i<=m;i++)
		if (!a[q[i].id]) a[q[i].id]=i;
			else b[q[i].id]=i;
	for (int i=1;i<=n;i++) q[q[a[i]].id=b[i]].id=a[i];
	nodes=1;build(1,1,m);
	int l=1,r=1000000000,ans=0;
	for (;l<=r;){
		int mid=(l+r)>>1;
		if (check(mid)) ans=mid,l=mid+1;
			else r=mid-1;
	}
	printf("%d\n",ans);
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:72:18: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d\n",&n);m=n*2;
                  ^
./Main.cpp:74:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&q[i*2-1].x,&q[i*2].x);
                                      ^

Judge Result