代码

#include <algorithm>
#include <stdio.h>
#include <vector>
typedef long long llt;
typedef unsigned uint;typedef unsigned long long ullt;
typedef bool bol;typedef char chr;typedef void voi;
typedef double dbl;
template<typename T>bol _max(T&a,T b){return(a<b)?a=b,true:false;}
template<typename T>bol _min(T&a,T b){return(b<a)?a=b,true:false;}
template<typename T>T lowbit(T n){return n&-n;}
template<typename T>T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<typename T>T lcm(T a,T b){return(a!=0||b!=0)?a/gcd(a,b)*b:(T)0;}
template<typename T>T exgcd(T a,T b,T&x,T&y){if(b!=0){T ans=exgcd(b,a%b,y,x);y-=a/b*x;return ans;}else return y=0,x=1,a;}
template<typename T>T power(T base,T index,T mod)
{
    T ans=1%mod;
    while(index)
    {
        if(index&1)ans=ans*base%mod;
        base=base*base%mod,index>>=1;
    }
    return ans;
}
struct Kosaraju
{
    std::vector<std::vector<uint> >Way,RWay;
    std::vector<uint>Own,Stack;
    uint size(){return Way.size();}
    voi build(uint n){Way.clear(),RWay.clear(),Own.clear(),Stack.clear(),Way.resize(n),RWay.resize(n);}
    voi insert(uint u,uint v){Way[u].push_back(v),RWay[v].push_back(u);}
    voi dfs1(uint p,std::vector<bol>&Gone){
        if(Gone[p])return;
        Gone[p]=true;
        for(auto s:Way[p])dfs1(s,Gone);
        Stack.push_back(p);
    }
    voi dfs2(uint p,uint id,std::vector<bol>&Gone){
        if(!Gone[p])return;
        Own[p]=id;Gone[p]=false;
        for(auto s:RWay[p])dfs2(s,id,Gone);
    }
    uint run(){
        uint n=size();Own.resize(n),Stack.clear();
        std::vector<bol>Gone(n,false);for(uint i=0;i<n;i++)dfs1(i,Gone);
        uint cnt=0;for(uint i=n-1;~i;i--)if(Gone[Stack[i]])dfs2(Stack[i],cnt++,Gone);
        return cnt;
    }
}K;
typedef std::pair<uint,uint>Pair;
chr C[100005],W[2],Ans[100005];
std::vector<Pair>E;
const Pair p[3]={Pair(1,2),Pair(0,2),Pair(0,1)};
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
    freopen("QAQ.out","w",stdout);
#endif
    uint n,m,d;scanf("%u%u%s%u",&n,&d,C,&m);
    while(m--)
    {
        uint u,from,to;
        scanf("%u%s",&u,W);from=(u-1)*3+(*W-'A');
        scanf("%u%s",&u,W);to=(u-1)*3+(*W-'A');
        E.push_back({from,to});
    }
    uint w=1u<<d;
    for(uint S=0;S<w;S++)
    {
        uint T=S;
        K.build(n*6);
        for(uint i=0;i<n;i++){
            uint now;
            if(C[i]=='x')now=T&1,T>>=1;else now=C[i]-'a';
            Pair q=p[now];uint u=q.first,v=q.second;
            K.insert((i*3+u)<<1,(i*3+v)<<1|1),K.insert((i*3+u)<<1|1,(i*3+v)<<1);
            K.insert((i*3+v)<<1,(i*3+u)<<1|1),K.insert((i*3+v)<<1|1,(i*3+u)<<1);
            K.insert((i*3+now)<<1,(i*3+now)<<1|1);
        }
        for(auto e:E)K.insert(e.first<<1,e.second<<1),K.insert(e.second<<1|1,e.first<<1|1);
        K.run();
        bol op=true;
        for(uint i=0;i<n*3;i++)op&=K.Own[i<<1]!=K.Own[i<<1|1];
        if(op)
        {
            for(uint i=0;i<n;i++)Ans[i]=K.Own[i*6]>K.Own[i*6+1]?'A':(K.Own[i*6+2]>K.Own[i*6+3]?'B':'C');
            Ans[n]='\0';puts(Ans);return 0;
        }
    }
    puts("-1");
    return 0;
}

评测结果