这题卡常吗?
查看原帖
这题卡常吗?
182101
逆天峰王者楼主2020/5/14 18:56

为什么此题我开O2还是T掉8和10两个点???

//不等,不问,不犹豫,不回头.
#include<bits/stdc++.h>
#define _ 0
#define db double
#define RE register
#define ll long long
#define P 1000000007
#define INF 1000000000
#define get(x) x=read()
#define PLI pair<ll,int>
#define PII pair<int,int>
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
#define pb(x) push_back(x)
#define ull unsigned long long
#define put(x) printf("%d\n",x)
#define putl(x) printf("%lld\n",x)
#define rep(i,x,y) for(RE int i=x;i<=y;++i)
#define fep(i,x,y) for(RE int i=x;i>=y;--i)
#define go(x) for(int i=link[x],y=a[i].y;i;y=a[i=a[i].next].y)
using namespace std;
const int N=510;
int n,m,a[N][N],b[N],id[N][N],tot,cnt;
struct wy
{
	int l,r,u,d,col,x;
	#define l(x) t[x].l
	#define r(x) t[x].r
	#define u(x) t[x].u
	#define d(x) t[x].d
	#define x(y) t[y].x
	#define col(x) t[x].col
}t[N*N];


char buf[1<<15],*fs,*ft;
inline char getc() {return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
inline int read()
{
	int x=0,ff=1;
	char ch=getc();
	while(!isdigit(ch)) {if(ch=='-') ff=-1;ch=getc();}
	while(isdigit(ch)) {x=(x<<1)+(x<<3)+(ch^48);ch=getc();}
	return x*ff;
}

inline void prework()
{
	rep(i,1,m) l(i)=i-1,r(i)=i+1;
	l(0)=m;r(0)=1;r(m)=0;tot=m;
	rep(i,1,n) rep(j,1,m) if(a[i][j]) 
	{
		id[i][j]=++tot;
		x(tot)=i;
		col(tot)=j;
	}
	rep(i,1,n) 
	{
		int cnt=0;
		rep(j,1,m) if(a[i][j]) b[++cnt]=id[i][j];
		if(!cnt) continue;
		if(cnt==1) l(b[1])=r(b[1])=b[1];
		else
		{
			rep(j,1,cnt) l(b[j])=b[j-1],r(b[j])=b[j+1];
			l(b[1])=b[cnt];r(b[cnt])=b[1];
		}
	
	}
	rep(i,1,m)
	{
		int cnt=0;
		b[++cnt]=i;
		rep(j,1,n) if(a[j][i]) b[++cnt]=id[j][i];
		if(cnt==1) u(b[1])=d(b[1])=b[1];
		else
		{
			rep(j,1,cnt) u(b[j])=b[j-1],d(b[j])=b[j+1];
			u(b[1])=b[cnt];d(b[cnt])=b[1];
		}
	}
}

inline bool remove(int x)
{
	r(l(x))=r(x);l(r(x))=l(x);
	if(d(x)==x) return false;
	for(int i=d(x);i!=x;i=d(i))
		 for(int j=r(i);j!=i;j=r(j))
		 {
		 	d(u(j))=d(j);
		 	u(d(j))=u(j);
		 }
	return true;
}

inline void recover(int x)
{
	l(r(x))=x;r(l(x))=x;
	for(int i=d(x);i!=x;i=d(i))
		for(int j=r(i);j!=i;j=r(j)) d(u(j))=u(d(j))=j;
} 

inline bool DLX()
{
	int c=r(0);
	if(c==0) return true;
	if(!remove(c)) {recover(c);return false;} 
	for(int i=d(c);i!=c;i=d(i))
	{
		for(int j=r(i);j!=i;j=r(j)) remove(col(j));
		if(DLX())
		{
			printf("%d ",x(i));
			return true;
		}
		for(int j=r(i);j!=i;j=r(j)) recover(col(j));	
	}
	recover(c);
	return false;
} 

int main()
{
	//freopen("1.in","r",stdin);
	get(n);get(m);
	rep(i,1,n) rep(j,1,m) get(a[i][j]);
	prework();
	if(!DLX()) puts("No Solution!");
	return (0^_^0);
}

2020/5/14 18:56
加载中...