【2SAT+Trie】Gym101190B [NEERC2016] Binary Code

【タイトル】Gymはいくつかのバイナリ符号化を与え、各符号化はせいぜい1つの位置が何なのか分からない.他の符号化のプレフィックスである符号化が1つもないように補完符号化方式があるかどうかを尋ねる.n , ∑ ∣ s ∣ ≤ 5 × 1 0 5 n,\sum|s|\leq 5\times 10^5 n,∑∣s∣≤5×105
【解題の考え方】2つのうちの選択は実際には2-SATtext{2-SAT}2-SATモデルである.しかし、私たちが暴力的に図を作ると涼しくなるので、Trietext{Trie}Trieを使って図を作るのを補助することを考えて、すべての列を1本のTrietext{Trie}Trieの木を建てて、いずれかの根から葉への経路に相当して多くの点があれば、接頭辞で図を最適化することができます.そしてなくなったの?簡単だね
【参考コード】

#include
using namespace std;

const int N=5e6+10;

namespace Trie
{
	int sz,pos[N],fa[N],ch[N][2];
	void insert(char *s,int len,int p)
	{
		int now=0;
		for(int i=0;i<len;++i)
		{
			int x=s[i]^48;
			if(!ch[now][x]) ch[now][x]=++sz,fa[sz]=now;
			now=ch[now][x];
		}
		pos[p]=now;
	}
}
using namespace Trie;


namespace Graph
{
	int tot,top,scc,ind;
	int head[N],dfn[N],low[N],st[N],ins[N],bl[N];
	struct Tway{int v,nex;}e[N<<1];
	void add(int u,int v)
	{
		//printf("%d %d
",u,v);
		e[++tot]=(Tway){v,head[u]};head[u]=tot;
	}
	void tarjan(int x)
	{
		//printf("%d
",x);
		dfn[x]=low[x]=++ind;ins[x]=1;st[++top]=x;
		for(int i=head[x];i;i=e[i].nex)
		{
			int v=e[i].v;
			if(!dfn[v]) tarjan(v),low[x]=min(low[x],low[v]);
			else if(ins[v]) low[x]=min(low[x],dfn[v]);
		}
		if(dfn[x]^low[x]) return;
		//printf("%d
",top);
		int u=0;++scc;do{u=st[top--];ins[u]=0;bl[u]=scc;}while(top && u!=x);
	}
}
using namespace Graph;

namespace DreamLolita
{
	int n,fg[N];
	char s[N];
	vector<string>S;
	vector<int>vec[N];
	void solution()
	{
		scanf("%d",&n);
		for(int i=1;i<=n;++i)
		{
			scanf("%s",s);fg[i]=-1;
			int len=strlen(s);string now="";
			for(int j=0;j<len;++j) 
			{
				now+=s[j];
				if(s[j]=='?') fg[i]=j;
			}
			S.push_back(now);
			if(!~fg[i])
			{
				add(i<<1,i<<1|1);insert(s,len,i<<1|1);pos[i<<1]=pos[i<<1|1];
			}
			else 
			{
				s[fg[i]]='0';insert(s,len,i<<1);s[fg[i]]='1';insert(s,len,i<<1|1);
			}
		}
		int sum=(n<<1|1)+2;
		for(int i=1;i<=sz;++i) add(sum+(fa[i]<<1),sum+(i<<1)),add(sum+(i<<1|1),sum+(fa[i]<<1|1));
		for(int i=2;i<=(n<<1|1);++i)
		{
			vec[pos[i]].push_back(i);
			if(ch[pos[i]][0]) add(i,sum+(ch[pos[i]][0]<<1));
			if(ch[pos[i]][1]) add(i,sum+(ch[pos[i]][1]<<1));
			add(i,sum+(fa[pos[i]]<<1|1));add(sum+(pos[i]<<1),i^1);add(sum+(pos[i]<<1|1),i^1);
		}
		sum+=(sz<<1|1)+2;
		for(int i=1;i<=sz;++i)
		{
			if(!vec[i].size()) continue;
			add(vec[i][0],sum);add(sum+1,vec[i][0]^1);
			for(int j=1;j<(int)vec[i].size();++j)
			{
				add(sum+(j<<1|1),sum+((j-1)<<1|1));add(sum+((j-1)<<1),sum+(j<<1));
				add(vec[i][j],sum+(j<<1));add(sum+(j<<1|1),vec[i][j]^1);
				add(vec[i][j],sum+((j-1)<<1|1));add(sum+((j-1)<<1),vec[i][j]^1);
			}
			sum+=((int)vec[i].size()<<1|1)+2;
		}
		for(int i=1;i<=sum;++i) if(!dfn[i]) tarjan(i);
		//for(int i=1;i<=sum;++i) printf("%d ",bl[i]); puts("");
		for(int i=1;i<=n;++i) if(bl[i<<1]==bl[i<<1|1]) {puts("NO");return;}
		puts("YES");
		for(int i=1;i<=n;++i) 
		{	
			if(~fg[i]) S[i-1][fg[i]]=bl[i<<1|1]<bl[i<<1]?'1':'0';
			int len=S[i-1].length();
			for(int j=0;j<len;++j) putchar(S[i-1][j]); puts("");
		}
	}
}

int main()
{
	freopen("binary.in","r",stdin);
	freopen("binary.out","w",stdout);
	DreamLolita::solution();
	return 0;
}