RT

与std对拍大数据感觉速度差不太多，莫名奇妙的TLE

Code

#include<bits/stdc++.h>
using namespace std;
#define f(x) (x<=n?x+n:x-n)
#define il inline
const int M=5e6+10;
int tt;
struct NODE{
	string c;
	int len,pos,id;
}s[M];
int pos[M];
il bool cmp(const NODE &A,const NODE&B){
	if(A.pos||B.pos)return !(bool)A.pos;
	return A.len>B.len;
}
struct EDGE{
	int to,next;
}e[M<<1];
int head[M],ct=0;
il void add(int u,int v){
	ct++;
	e[ct]=EDGE{v,head[u]};
	head[u]=ct;
}
int n;
int cnt;
int r1,r2;
int c[M][2],ch[M][2],fa[M],tot;
bool bo[M];
vector<int>b[M],sq[M],sh[M];
il void insert(string &s){
//	cout<<"insert:"<<s<<endl;
	int len=s.size(),u=0;
	for(int i=0;i<len;i++){
		int c=s[i]-'0';
		if(!ch[u][c])ch[u][c]=++tot;
		u=ch[u][c];
	}
	bo[u]=1;
}
il bool check(string &s){
	int len=s.size(),u=0;
	for(int i=0;i<len;i++){
		int c=s[i]-'0';
		if(bo[u])return false;
		if(!ch[u][c])return true;
		u=ch[u][c];
	}
	return false;
}
il void insert(string &s,int p,int id){
	int u=(p==0?r1:r2),len=s.size();
	for(int i=0;i<len;i++){
		int nc=s[i]-'0';
		if(!c[u][nc]){
			c[u][nc]=++cnt;
			fa[cnt]=u;
			if(p==0)add(u,cnt);
			else add(cnt,u);
		}
		u=c[u][nc];
	}
	add(u,id);
	b[u].push_back(id);
}
il void add(string &s,int id){
	int u1=r1,u2=r2;
	int len=s.size();
	for(int i=0;i<len;i++){
		int nc=s[i]-'0';
		u1=c[u1][nc];
		u2=c[u2][nc];
	}
	if(c[u1][0])add(id,c[u1][0]);
	if(c[u1][1])add(id,c[u1][1]);
	if(fa[u2])add(id,fa[u2]);
	len=b[u1].size();
	for(int i=0;i<len;i++){
		if(f(b[u1][i])==id){
			if(i>0)add(id,sq[u1][i-1]);
			if(i<len-1)add(id,sh[u1][i+1]);
			break;
		}
	}
}
int dfn[M],low[M],col[M],tim,snt;
int st[M],top;
il void tarjan(int u){
	dfn[u]=low[u]=++tim;
	st[++top]=u;
	for(int i=head[u];i;i=e[i].next){
		int v=e[i].to;
		if(!dfn[v]){
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}else if(!col[v])low[u]=min(low[u],dfn[v]);
	}
	if(low[u]==dfn[u]){
		snt++;
		while(st[top+1]!=u)col[st[top--]]=snt;
	}
}
char cs[M];
string ans[M];
signed main(){
//	freopen("temp.in","r",stdin);
//	freopen("temp.out","w",stdout);
//	ios::sync_with_stdio(0);
//	cin.tie(0);
//	cout.tie(0);
	cin>>n;
	cnt=2*n;
	r1=++cnt,r2=++cnt;
	for(int i=1;i<=n;i++){
		scanf("%s",(cs+1));
		int len=strlen(cs+1);
		for(int j=1;j<=len;j++)s[i].c+=cs[j];
		s[i].len=len;
		for(int j=0;j<s[i].len;j++){
			if(s[i].c[j]=='?'){
				s[i].pos=j+1;
				break;
			}
		}
		s[i].id=i;
	}
	sort(s+1,s+n+1,cmp);
	for(int i=1;i<=n;i++){
		if(s[i].pos){
			s[i].c[s[i].pos-1]='0';
			bool p1=check(s[i].c);
			s[i].c[s[i].pos-1]='1';
			bool p2=check(s[i].c);
			if(p1&&p2)pos[++tt]=i;
			else if(p1)s[i].c[s[i].pos-1]='0',insert(s[i].c),ans[s[i].id]=s[i].c;
			else if(p2)s[i].c[s[i].pos-1]='1',insert(s[i].c),ans[s[i].id]=s[i].c;
			else{
				puts("NO");
				return 0;
			}
		}else{
			ans[s[i].id]=s[i].c;
			if(check(s[i].c))insert(s[i].c);
			else{
				puts("NO");
				return 0;
			}
		}
	}
//	cout<<"tt:"<<tt<<endl;
	for(int i=1;i<=tt;i++){
		int np=pos[i];
		s[np].c[s[np].pos-1]='0';
		insert(s[np].c,0,i+n);
		insert(s[np].c,1,i+n);
		s[np].c[s[np].pos-1]='1';
		insert(s[np].c,0,i);
		insert(s[np].c,1,i);
	}
	for(int i=1;i<=cnt;i++){
		if(!b[i].empty()){
			int len=b[i].size()-1;
			sq[i].resize(len+1),sh[i].resize(len+1);
			add(sq[i][0]=++cnt,b[i][0]);
			for(int k=1;k<=len;k++){
				int ns=sq[i][k]=++cnt;
				add(ns,sq[i][k-1]),add(ns,b[i][k]);
			}
			add(sh[i][len]=++cnt,b[i][len]);
			for(int k=len-1;k>=0;k--){
				int ns=sh[i][k]=++cnt;
				add(ns,sh[i][k+1]),add(ns,b[i][k]);
			}
		}
	}
	for(int i=1;i<=tt;i++){
		int np=pos[i];
		s[np].c[s[np].pos-1]='0';
		add(s[np].c,i);
		s[np].c[s[np].pos-1]='1';
		add(s[np].c,i+n);
	}
	for(int i=1;i<=2*n;i++){
		top=0;
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=tt;i++){
		int np=pos[i];
		ans[s[np].id]=s[np].c;
		if(col[i]<col[i+n])ans[s[np].id][s[np].pos-1]='0';
		else if(col[i]>col[i+n])ans[s[np].id][s[np].pos-1]='1';
		else{
			puts("NO");
			return 0;
		}
	}
	puts("YES");
	for(int i=1;i<=n;i++)cout<<ans[i]<<endl;
	return 0;
}