[NOI 2015]小园丁与老司机 - 神利·代目 - 245310

记录编号	245310	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOI 2015]小园丁与老司机	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	3.966 s
提交时间	2016-04-02 21:45:14	内存使用	134.39 MiB
显示代码纯文本
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define inf 0x3fffffff
int n,L[500100],R[500100];
inline int MIN(int A,int B){return A<B?A:B;}
inline int MAX(int A,int B){return A>B?A:B;}
struct node{int x,y,he,cha,id,orid;}a[500100];
inline bool comp_x(node a,node b){return a.x==b.x?a.y<b.y:a.x<b.x;}
inline bool comp_y(node a,node b){return a.y==b.y?a.x<b.x:a.y<b.y;}
inline bool comp_he(node a,node b){return a.he==b.he?a.y<b.y:a.he<b.he;}
inline bool comp_cha(node a,node b){return a.cha==b.cha?a.y<b.y:a.cha<b.cha;}
int shu,first[500100],firs[500100];
struct edge{int v,w,nx;}o[2100000],e[2100000],O[4100000];
inline void add(int u,int v){
	o[++shu].v=v,o[shu].nx=first[u],first[u]=shu;
	e[shu].v=u,e[shu].nx=firs[v],firs[v]=shu;
}
int SHU,FIRST[500100];
inline void ADD(int u,int v,int w){
	O[++SHU].v=v,O[SHU].w=w,O[SHU].nx=FIRST[u],FIRST[u]=SHU;
}
int ans,f[500100],g[500100],f2[500100],g2[500100],nx[500100][2];
void init(){
	scanf("%d",&n),++n;
	for(int i=1;i<n;++i) scanf("%d%d",&a[i].x,&a[i].y),a[i].he=a[i].x+a[i].y,a[i].cha=a[i].x-a[i].y,a[i].orid=i;
	std::sort(a,a+n,comp_y);
	for(int i=0;i<n;++i,f[i]=-inf) a[i].id=i;
	for(int i=1,last=0;i<n;++i){
		if(a[i].y!=a[last].y) L[++L[0]]=last,R[L[0]]=i-1,last=i;
		if(i==n-1) L[++L[0]]=last,R[L[0]]=i;
	}
	std::sort(a,a+n,comp_x);
	for(int i=1;i<n;++i)
	    if(a[i].x==a[i-1].x)
	        add(a[i-1].id,a[i].id);
	std::sort(a,a+n,comp_he);
	for(int i=1;i<n;++i)
	    if(a[i].he==a[i-1].he)
	        add(a[i-1].id,a[i].id);
	std::sort(a,a+n,comp_cha);
	for(int i=1;i<n;++i)
	    if(a[i].cha==a[i-1].cha)
	        add(a[i-1].id,a[i].id);
}
void dp(){
	std::sort(a,a+n,comp_y);
	for(int i=1,mx;i<=L[0];++i){
		for(int j=L[i],mx=-inf;j<=R[i];++j){
			g[j]=MAX(mx+j-L[i]+1,f[j]+1);
			for(int k=first[j];k;k=o[k].nx)
				if(f[o[k].v]<g[j])
				    f[o[k].v]=g[j];
			mx=MAX(mx,f[j]);
		}
		for(int j=R[i],mx=-inf;j>=L[i];--j){
			g[j]=MAX(g[j],MAX(mx+R[i]-j+1,f[j]+1));
			for(int k=first[j];k;k=o[k].nx)
				if(f[o[k].v]<g[j])
				    f[o[k].v]=g[j];
			mx=MAX(mx,f[j]);
		}
	}
	for(int i=L[0];i;--i){
		for(int j=R[i],mx=-inf,now;j>=L[i];--j){
			if(g2[j]<=f2[j]+1) g2[j]=f2[j]+1,nx[j][1]=j;
			if(g2[j]<=mx) g2[j]=mx,nx[j][1]=now;
			for(int k=firs[j];k;k=e[k].nx)
				if(f2[e[k].v]<g2[j])
				    f2[e[k].v]=g2[j],nx[e[k].v][0]=j;
			if(mx<f2[j]+j-L[i]+1) mx=f2[j]+j-L[i]+1,now=j;
		}
		for(int j=L[i],mx=-inf,now;j<=R[i];++j){
			if(g2[j]<=f2[j]+1) g2[j]=f2[j]+1,nx[j][1]=j;
			if(g2[j]<=mx) g2[j]=mx,nx[j][1]=now;
			for(int k=firs[j];k;k=e[k].nx)
				if(f2[e[k].v]<=g2[j])
				    f2[e[k].v]=g2[j],nx[e[k].v][0]=j;
			if(mx<f2[j]+R[i]-j+1) mx=f2[j]+R[i]-j+1,now=j;
		}
	}
	ans=g2[0];
	printf("%d\n",ans-1);
}
void path(){
	int now=0,tmp;
	while(nx[now][0]||nx[nx[now][0]][1]){
		now=nx[now][0];
		if(now==nx[now][1]) printf("%d ",a[now].orid);
		else{
			if(a[nx[now][1]].x<a[now].x){
				tmp=now;
				while(a[tmp].y==a[now].y) printf("%d ",a[tmp].orid),++tmp;
				tmp=now-1;
				while(tmp!=nx[now][1]) printf("%d ",a[tmp].orid),--tmp;
			}else{
				tmp=now;
				while(a[tmp].y==a[now].y) printf("%d ",a[tmp].orid),--tmp;
				tmp=now+1;
				while(tmp!=nx[now][1]) printf("%d ",a[tmp].orid),++tmp;
			}
			printf("%d ",a[now=nx[now][1]].orid);
		}
	}
}
bool flag[500100][2];
int S,T,ru[500100];
void build(){
	SHU=1;
	S=n+2,T=n+3;
	int s=n,t=n+1;
	for(int i=1;i<=shu;++i)
	    if(g[e[i].v]+g2[o[i].v]==ans){
			ADD(e[i].v,o[i].v,inf),ADD(o[i].v,e[i].v,0),++ru[o[i].v],--ru[e[i].v];
			if(!flag[e[i].v][0]) ADD(s,e[i].v,inf),ADD(e[i].v,s,0),flag[e[i].v][0]=1;
			if(!flag[o[i].v][1]) ADD(o[i].v,t,inf),ADD(t,o[i].v,0),flag[o[i].v][1]=1;
	    }
	for(int i=0;i<=t;++i)
	    if(ru[i]>0) ADD(S,i,ru[i]),ADD(i,S,0);
	    else if(ru[i]<0) ADD(i,T,-ru[i]),ADD(T,i,0);
}
int l,r,d[500100],q[500100];
inline bool BFS(int s,int t){
	memset(d,0,sizeof(d));
	q[l=r=0]=s,d[s]=1;
	while(l<=r){
		s=q[l++];
		for(int i=FIRST[s];i;i=O[i].nx)
		    if(O[i].w&&!d[O[i].v]){
				d[O[i].v]=d[s]+1;
				if(O[i].v==t) return 1;
				q[++r]=O[i].v;
		    }
	}
	return 0;
}
inline int DFS(int x,int t,int flow){
	if(x==t) return flow;
	int tmp=flow,k;
	for(int i=FIRST[x];i&&tmp;i=O[i].nx)
	    if(O[i].w&&d[O[i].v]==d[x]+1){
			k=DFS(O[i].v,t,MIN(tmp,O[i].w));
			if(!k) d[O[i].v]=0;
			tmp-=k,O[i].w-=k,O[i^1].w+=k;
	    }
	return flow-tmp;
}
void DINIC(){
	int maxflow=0,flow;
	while(BFS(S,T)) while(flow=DFS(S,T,inf)) maxflow+=flow;
	ans=maxflow;
}
int main(){
	freopen("farm.in","r",stdin);
	freopen("farm.out","w",stdout);
	init();
	dp();
	path();
	build();
	DINIC();
	ADD(n+1,n,inf),ADD(n,n+1,0);
	DINIC();
	printf("\n%d",ans);
}