codeforces 569 E. New Language (2-sat)

/*************************************************************************
  > File Name: code/cf/#315/E.cpp
  > Author: 111qqz
  > Email: rkz2013@126.com 
  > Created Time: 2015年08月15日 星期六 13时48分36秒
 ************************************************************************/
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<string>
#include<map>
#include<set>
#include<queue>
#include<vector>
#include<stack>
#define y0 abc111qqz
#define y1 hust111qqz
#define yn hez111qqz
#define j1 cute111qqz
#define tm crazy111qqz
#define lr dying111qqz
using namespace std;
#define REP(i, n) for (int i=0;i<int(n);++i)  
typedef long long LL;
typedef unsigned long long ULL;
const int inf = 0x7fffffff;
const int N=5E2+7;
int flag[N],flag2[N];
int f[N][N];
int a[N];
char s[N];
int ans[N];
int len,n,m;
char s1[13],s2[13];
int p1,p2,q1,q2,dq1,dq2;
void add(int p,int q,int flag[])
{
    int dq = q * n + p;//找到元辅音状态为q,第p的点的下标
    for (int i=1;i<=2*n;++i)
    {
	if (f[dq][i]==0) continue;
	flag[i]=1;//找到所有由dp出发的边指向的点,表示选了dp点一定要选的点。
    }
} 
bool check(int flag[])
{
    for (int i=1;i<=n;++i) 
	if (flag[i]==1&&flag[i+n]==1) return false; //判断是否存在矛盾
    //(选了j点后,既要选择某点k的元音,也要选择某点k的辅音) 
    return true;
}
bool dfs(int pos,int x)
{
    if (pos>n) return true;//如果能形成一个长度为n的单词,说明这种语言有word
    bool g[2];
    g[0]=g[1]=false;
    for (int i=x;i<=len;++i)//从当前字母x往后枚举
    {
	for (int j=1;j<=2*n;++j) flag2[j]=flag[j];//为了不影响原始数组,复制一个布尔数组出来。
	add(pos,a[i],flag2);//找到所有选了pos点一定要选的点
	if (check(flag2)&&(!g[a[i]]))
	{
	    g[a[i]]=true;
	    for (int j=1;j<=2*n;++j) flag[j]=flag2[j];
	    ans[pos]=i;//将第pos位置的字母变成i
	    if (dfs(pos+1,1)) return true; 
	    else return false;//只要有一位找不到合适的字母形成单词,那么肯定就构不成单词。
	}
    }
    return false;
}
int main()
{
    scanf("%s",s);
    len=strlen(s);           //0表示辅音,1表示原因,下同。
    for (int i=1;i<=len;++i)//len 表示字母表中一共有的字母的个数
    {
	if (s[i-1]=='V')
	{
	    a[i] = 0;
	}
	else
	{
	    a[i]  = 1;
	}
    }
    memset(f,0,sizeof(f));
    scanf("%d%d",&n,&m);
    for (int i=1;i<=m;++i)//1..n表示元音的点,n+1..2*n 表示辅音的点
    {
	scanf("%d",&p1);
	scanf("%s",s1);
	if (s1[0]=='V') q1=0;else q1=1;
	scanf("%d",&p2);
	scanf("%s",s2);
	if (s2[0]=='V') q2=0;else q2=1;
	dq1=q1*n+p1;dq2=q2*n+p2;//找到这组关系对应的点。
	f[dq1][dq2]=1;//连一条由dq1指向dq2的边,表示如果选了dp1点,那么一定选dp2点   
	dq1=(1-q2)*n+p2;dq2=(1-q1)*n+p1;//找到逆否命题对应的点 
	// ("如果选1,一定选2"的逆否命题是,"如果不选2,一定不选1")
	f[dq1][dq2]=1;      //在连一条边
    }
    for (int i=1;i<=2*n;++i) f[i][i]=1;
    for (int k=1;k<=2*n;++k)//floyd ,把所有间接相连的边直接相连
    {
	for (int i=1;i<=2*n;++i)
	    for (int j=1;j<=2*n;++j)
		f[i][j]|=f[i][k]&f[k][j];
    }
    scanf("%s",s+1);
    bool ok=false;
    for (int i=n;i>=0;--i) //倒着扫,每次只改变最后一位的字母,字母从小往大枚举 //这样就可以保证字典序最小。
    {
	memset(flag,0,sizeof(flag));
	for (int j=1;j<=i;++j) 
	{
	    add(j,a[s[j]-'a'+1],flag);	
	    ans[j]=s[j]-'a'+1;
	}
	if (!check(flag)) continue;
	if (dfs(i+1,s[i+1]-'a'+1+1))
	{
	    ok=true;
	    break;
	}		
    }
    if (!ok) printf("-1\n");
    else
    {
	for (int i=1;i<=n;++i) printf("%c",ans[i]+'a'-1);
    }
    return 0;
}