【BZOJ4945】[Noi2017]游戏

#include <cstdio>#include <cstring>#include <iostream>#include <queue>#define P(A,B) ((B-1)*n+A)using namespace std;const int maxn=200010;int n,D,m,sum,tot,top,cnt,flag;int to[maxn],next[maxn],head[maxn],tt[maxn],nn[maxn],hh[maxn],op[maxn],ot[maxn];int del[maxn],ins[maxn],dep[maxn],low[maxn],sta[maxn],bel[maxn],pos[10];int pa[maxn],pb[maxn],pc[maxn],pd[maxn],color[maxn],d[maxn];char str[maxn],c1[5],c2[5],ans[maxn];queue<int> q;void add(int a,int b){	to[cnt]=b,next[cnt]=head[a],head[a]=cnt++;}void ADD(int a,int b){	tt[cnt]=b,nn[cnt]=hh[a],hh[a]=cnt++;}void tarjan(int x){	dep[x]=low[x]=++tot,ins[x]=1,sta[++top]=x;	for(int i=hh[x];i!=-1;i=nn[i])	{		int y=tt[i];		if(!dep[y])	tarjan(y),low[x]=min(low[x],low[y]);		else	if(ins[y])	low[x]=min(low[x],dep[y]);	}	if(dep[x]==low[x])	{		int t;		sum++;		do		{			t=sta[top--],ins[t]=0,bel[t]=sum;		}while(t!=x);	}}void check(){	memset(hh,-1,sizeof(hh));	memset(dep,0,sizeof(dep));	cnt=tot=sum=0;	int i,a,b,c;	for(i=1;i<=n;i++)	{		a=(str[i]-‘a‘)*n+i,b=(a-1+n)%(3*n)+1,c=(b-1+n)%(3*n)+1;		del[a]=1,del[b]=del[c]=0;		op[b]=c,op[c]=b;	}	for(i=1;i<=m;i++)	{		a=pc[i]*n+pa[i],b=pd[i]*n+pb[i];		if(a==b||del[a])	continue;		if(pa[i]==pb[i]||del[b])		{			ADD(a,op[a]);			continue;		}		ADD(op[b],op[a]),ADD(a,b);	}	for(i=1;i<=3*n;i++)	if(!del[i]&&!dep[i])	tarjan(i);	for(i=1;i<=3*n;i++)	{		if(del[i])	continue;		if(bel[op[i]]==bel[i])	return ;		else	ot[bel[op[i]]]=bel[i],ot[bel[i]]=bel[op[i]];	}	flag=1;}void dfs(int x){	if(x==D+1)	{		check();		return ;	}	str[pos[x]]=‘a‘,dfs(x+1);	if(flag)	return ;	str[pos[x]]=‘b‘,dfs(x+1);}void DFS(int x){	if(color[x]!=-1)	return ;	color[x]=0,color[ot[x]]=1;	for(int i=head[x];i!=-1;i=next[i])	DFS(to[i]);}int main(){	scanf("%d%d%s%d",&n,&D,str+1,&m);	int i,j,u;	for(i=1;i<=n;i++)	if(str[i]==‘x‘)	pos[++pos[0]]=i;	for(i=1;i<=m;i++)	{		scanf("%d%s%d%s",&pa[i],c1,&pb[i],c2),pc[i]=c1[0]-‘A‘,pd[i]=c2[0]-‘A‘;	}	dfs(1);	if(!flag)	{		printf("-1");		return 0;	}	memset(head,-1,sizeof(head));	memset(color,-1,sizeof(color));	cnt=0;	for(i=1;i<=3*n;i++)	if(!del[i])	{		for(j=hh[i];j!=-1;j=nn[j])	if(bel[tt[j]]!=bel[i])	d[bel[i]]++,add(bel[tt[j]],bel[i]);	}	for(i=1;i<=sum;i++)	if(!d[i])	q.push(i);	while(!q.empty())	{		u=q.front(),q.pop();		for(i=head[u];i!=-1;i=next[i])		{			d[to[i]]--;			if(!d[to[i]])	q.push(to[i]);		}		if(color[u]!=-1)	continue;		DFS(ot[u]);	}	for(i=1;i<=3*n;i++)	if(!del[i]&&color[bel[i]]==1)	ans[(i-1)%n]=(i-1)/n+‘A‘;	printf("%s",ans);	return 0;}