嘟嘟嘟
这题也太暴力了……
考虑如果没有'x'的情况，那就是2-SAT水题。有了'x'怎么办？因为'x'最多只有8个，所以我们暴力枚举，时间复杂度(O((n + m) * 3 ^ 8))。这算出来后大约是(9e8)，所以就没敢写……
然而这实际上根本跑不满，找到合法的就exit(0)，几乎每一个点不到200ms就跑出来了……
不过有一个地方还是要讲一下的，就是如果赛道(i)选了(h_i)车，则(j)就得选(h_j)。首先如果(h_i)不存在，不连边；如果(h_j)不存在。连边(i -> i')，表示选了(i)就gg；否则要连两条边，分别是(i->j)和(j' ->i')，刚开始我觉得第二条不用连，毕竟选(h_j)不选(h_i)是可以的。但我们得考虑2-SAT的对称性，即如果(j)不选(h_j)，则(i)只能选除(h_i)之外的另一辆。
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 5e4 + 5;
const int maxe = 4e5 + 5;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
In void MYFILE()
{
#ifndef mrclr
freopen("game.in", "r", stdin);
freopen("game.out", "w", stdout);
#endif
}
char s[maxn], c1[2], c2[2], asc[maxn << 1];
int n, d, m;
struct Node
{
int x; char c1; int y; char c2;
}q[maxn << 1];
int h[maxn][3], a[maxn], cnt = 0;
In void init()
{
for(int i = 1; i <= n; ++i)
{
if(s[i] == 'x') a[++cnt] = i;
else if(s[i] == 'a') h[i][1] = i, h[i][2] = n + i, asc[i] = 'B', asc[i + n] = 'C';
else if(s[i] == 'b') h[i][0] = i, h[i][2] = n + i, asc[i] = 'A', asc[i + n] = 'C';
else if(s[i] == 'c') h[i][0] = i, h[i][1] = n + i, asc[i] = 'A', asc[i + n] = 'B';
}
}
struct Edge
{
int nxt, to;
}e[maxe];
int head[maxn << 1], ecnt = -1;
In void addEdge(int x, int y)
{
e[++ecnt] = (Edge){head[x], y};
head[x] = ecnt;
}
bool in[maxn << 1];
int st[maxn << 1], top = 0;
int dfn[maxn << 1], low[maxn << 1], dcnt = 0;
int col[maxn << 1], ccol = 0;
In void tarjan(int now)
{
st[++top] = now; in[now] = 1;
dfn[now] = low[now] = ++dcnt;
for(int i = head[now], v; ~i; i = e[i].nxt)
{
if(!dfn[v = e[i].to])
{
tarjan(v);
low[now] = min(low[now], low[v]);
}
else if(in[v]) low[now] = min(low[now], dfn[v]);
}
if(low[now] == dfn[now])
{
int x; ++ccol;
do
{
x = st[top--]; in[x] = 0;
col[x] = ccol;
}while(x ^ now);
}
}
In void build()
{
for(int i = 1; i <= m; ++i)
{
int u = h[q[i].x][q[i].c1 - 'A'], v = h[q[i].y][q[i].c2 - 'A'];
if(!u) continue;
if(!v) addEdge(u, u > n ? u - n : u + n);
else addEdge(u, v), addEdge(v > n ? v - n : v + n, u > n ? u - n : u + n);
}
}
In void clear()
{
ecnt = -1; top = dcnt = ccol = 0;
Mem(head, -1), Mem(dfn, 0), Mem(low, 0), Mem(in, 0);
}
In bool check()
{
clear(), build();
for(int i = 1; i <= (n << 1); ++i) if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; ++i)
if(col[i] == col[i + n]) return 0;
return 1;
}
In void print()
{
for(int i = 1; i <= n; ++i)
putchar(col[i] < col[i + n] ? asc[i] : asc[i + n]);
enter;
}
In void dfs_bf(int now)
{
if(now == cnt + 1)
{
if(check()) print(), exit(0);
return;
}
for(int i = 0; i < 3; ++i)
{
h[a[now]][(i + 2) % 3] = a[now], asc[a[now]] = 'A' + (i + 2) % 3;
h[a[now]][(i + 1) % 3] = a[now] + n, asc[a[now] + n] = 'A' + (i + 1) % 3;
h[a[now]][i] = 0;
dfs_bf(now + 1);
}
}
int main()
{
MYFILE();
Mem(head, -1);
n = read(), d = read(); scanf("%s", s + 1);
m = read();
for(int i = 1; i <= m; ++i)
{
int x = read(); scanf("%s", c1); int y = read(); scanf("%s", c2);
q[i] = (Node){x, c1[0], y, c2[0]};
}
init();
dfs_bf(1);
puts("-1");
return 0;
}