DLX TLE求助
查看原帖
DLX TLE求助
214728
剑雪清寒楼主2022/9/1 15:13

rt,数据下下来本地秒出,洛谷全TLE?为什么啊(((

#include <bits/stdc++.h>
struct stack {
	int the_stack[501],sum=0;
	inline int top() { return the_stack[sum-1]; }
	inline int pop() { return sum ? the_stack[--sum] : -1; }
	inline int push(int x) { the_stack[sum++]=x; }
	inline int operator[](const int &x) const{
		return the_stack[x-1];
	}
	inline void clear() { sum=0; }
}st;
inline long long read() {
	long long x;bool f;char ch;
	for(f=0;!isdigit(ch=getchar());f=ch=='-');
	for(x=ch-48;isdigit(ch=getchar());x=x*10+ch-48);
	return f?-x:x;
}
inline void print(long long x,char las) {
	if(!x) {
		putchar(48),putchar(las);
		return ;
	}
	if(x<0) putchar('-'),x=-x;
	int ls[20],k=0;
	while(x) ls[++k]=x%10,x/=10;
	while(k) putchar(ls[k--]+48);
	putchar(las);
	return ; 
}
struct node {
	node *left,*right,*down,*up,*col;int row,sum;
}nd[5001],head,c[501];
int n=read(),m=read(),cnt;
inline void delet(node *c) {
//	return ;
	c->right->left=c->left;c->left->right=c->right;
	for(node *i=c->down;i!=c;i=i->down) {
		for(node *j=i->right;j!=i;j=j->right) {
			j->down->up=j->up;j->up->down=j->down;j->col->sum--;
		}
	}
	return ;
}
inline void recover(node *c) {
//	return ;
	for(node *i=c->down;i!=c;i=i->down) {
		for(node *j=i->right;j!=i;j=j->right) {
			j->down->up=j->up->down=j;j->col->sum++;
		}
	}
	c->right->left=c->left->right=c;
	return ;
}
int ss;
inline bool dancing() {
	if(head.right==&head) {
		return true;
	}
	node *del=head.right;
	for(node *i=del;i!=&head;i=i->right) if(i->sum<del->sum) del=i;
	delet(del);
//	ss--;
	for(node *i=del->down;i!=del;i=i->down) {
		st.push(i->row);
		for(node *j=i->right;j!=i;j=j->right) delet(j->col)/*,ss--*/;
//		print(ss,'\n');
		if(dancing()) return true;
		st.pop();
		for(node *j=i->right;j!=i;j=j->right) recover(j->col)/*,ss++*/;
	}
//	ss++;
	recover(del);
	return false;
}
inline void solve() {
	if(dancing()) {
		while(st.sum) print(st.pop(),' ');
	}else puts("No Solution!");
	return ;
}
int main() {
	ss=m;
	head.right=&c[1];head.left=&c[m];
	for(int i=1;i<=m;i++) c[i].right=&c[i+1],c[i].left=&c[i-1],c[i].up=c[i].down=&c[i];
	c[1].left=c[m].right=&head;
	for(int i=1;i<=n;i++) {
		node *ls=0;
		for(int j=1;j<=m;j++) {
			int now=read();
			if(now) {
				c[j].sum++;
				if(!ls) {
					nd[++cnt].left=&nd[cnt];nd[cnt].right=&nd[cnt];
					ls=&nd[cnt];
				}else nd[++cnt].left=ls->left,nd[cnt].right=ls,ls->left->right=&nd[cnt],ls->left=&nd[cnt];
				nd[cnt].row=i;nd[cnt].col=&c[j];
				nd[cnt].up=c[j].up;nd[cnt].down=&c[j];c[j].up->down=&nd[cnt];c[j].up=&nd[cnt];
			}
		}
	}
	/*for(node *i=head.right;i!=&head;i=i->right) {
		print(i-c,' ');
	}*/
	/*for(int i=1;i<=m;i++) {
		for(node *j=c[i].down;j!=&c[i];j=j->down) {
			print(j->row,' ');
		}
		puts("");
	}*/
	solve();
	return 0;
}

2022/9/1 15:13
加载中...