代码

// This code is AI-generated. (AI 生成的代码)
// NOI2017 游戏: enumerate the two usable types for every 'x' track (2^d cases),
// then solve the resulting 2-SAT with Tarjan.
#include <sys/auxv.h>
#include <cstdio>
#include <cstring>

static const int MAXN = 50005, MAXE = 200005;
static int n, D, m, nx;
static int ft[MAXN];          // forbidden type of a track: 0=A,1=B,2=C, 3=x
static int xp[10];
static int cu[MAXE], cv[MAXE], ci[MAXE], cj[MAXE];
static int all[MAXN][2];      // the two usable types of a track
static int head[2 * MAXN], nxt[4 * MAXE], to[4 * MAXE], tc;
static int dfn[2 * MAXN], low[2 * MAXN], stk[2 * MAXN], in[2 * MAXN], comp[2 * MAXN];
static int timer, scc, top;

static inline void add_edge(int u, int v) {
    to[++tc] = v; nxt[tc] = head[u]; head[u] = tc;
}

static void tarjan(int u) {
    dfn[u] = low[u] = ++timer;
    stk[++top] = u; in[u] = 1;
    for (int e = head[u]; e; e = nxt[e]) {
        int v = to[e];
        if (!dfn[v]) { tarjan(v); if (low[v] < low[u]) low[u] = low[v]; }
        else if (in[v] && dfn[v] < low[u]) low[u] = dfn[v];
    }
    if (low[u] == dfn[u]) {
        ++scc;
        int v;
        do { v = stk[top--]; in[v] = 0; comp[v] = scc; } while (v != u);
    }
}

// node of literal "track i runs type t"; node 2i = first usable, 2i+1 = second
static inline int lit(int i, int t) {
    return all[i][0] == t ? (2 * (i - 1) + 1) : (2 * (i - 1));
}

static char res[50005];
struct DuckInfo {
    unsigned long abi; const char *in; unsigned long in_size;
    char *out; unsigned long out_limit, out_size;
    char *err; unsigned long err_limit, err_size;
    const char *IB; unsigned long IB_limit; char *OB; unsigned long OB_limit; unsigned long tsc;
} __attribute__((packed));
static const char *ip; static char *op;
static inline int rd() {
    const char *q = ip;
    while ((unsigned)(*q - '0') > 9u && *q != '-') q++;
    int neg = 0; if (*q == '-') { neg = 1; q++; }
    int x = 0;
    do { x = x * 10 + (*q++ - '0'); } while ((unsigned)(*q - '0') <= 9u);
    ip = q; return neg ? -x : x;
}
static inline char rch() {
    while (*ip && (unsigned char)*ip <= 32u) ip++;
    return *ip++;
}

int main() {
    struct DuckInfo *d = (struct DuckInfo *)getauxval(0x6b637564UL);
    ip = d->in; op = d->out;
    n = rd(); D = rd();
    static char s[50005];
    { while (*ip && (unsigned char)*ip <= 32u) ip++; for (int i = 1; i <= n; i++) s[i] = *ip++; }
    for (int i = 1; i <= n; i++) {
        char c = s[i];
        if (c == 'x') { xp[nx++] = i; ft[i] = 3; }
        else ft[i] = c - 'a';
    }
    m = rd();
    static char u[4], v[4];
    for (int k = 0; k < m; k++) {
        ci[k] = rd(); u[0] = rch(); cj[k] = rd(); v[0] = rch();
        cu[k] = u[0] - 'A'; cv[k] = v[0] - 'A';
    }

    for (int i = 1; i <= n; i++) {
        if (ft[i] == 3) continue;
        if (ft[i] == 0) { all[i][0] = 1; all[i][1] = 2; }
        else if (ft[i] == 1) { all[i][0] = 0; all[i][1] = 2; }
        else { all[i][0] = 0; all[i][1] = 1; }
    }

    int total = 1 << nx;
    for (int mask = 0; mask < total; mask++) {
        for (int k = 0; k < nx; k++) {
            int i = xp[k];
            all[i][0] = 0;
            all[i][1] = ((mask >> k) & 1) ? 2 : 1;
        }
        memset(head, 0, sizeof(int) * (2 * n + 1));
        tc = 0;
        for (int k = 0; k < m; k++) {
            int i = ci[k], uu = cu[k], j = cj[k], vv = cv[k];
            if (uu != all[i][0] && uu != all[i][1]) continue;
            int ni = lit(i, uu);
            if (vv == all[j][0] || vv == all[j][1]) { int nj = lit(j, vv); add_edge(ni, nj); add_edge(nj ^ 1, ni ^ 1); }
            else add_edge(ni, ni ^ 1);
        }
        memset(dfn, 0, sizeof(int) * (2 * n));
        timer = scc = top = 0;
        for (int i = 0; i < 2 * n; i++) if (!dfn[i]) tarjan(i);
        int ok = 1;
        for (int i = 1; i <= n; i++) if (comp[2 * (i - 1)] == comp[2 * (i - 1) + 1]) { ok = 0; break; }
        if (!ok) continue;
        for (int i = 1; i <= n; i++) {
            int b = (comp[2 * (i - 1)] < comp[2 * (i - 1) + 1]) ? 1 : 0;
            res[i - 1] = (char)('A' + all[i][b]);
        }
        for (int i = 0; i < n; i++) *op++ = res[i];
        *op++ = '\n';
        d->out_size = (unsigned long)(op - d->out);
        return 0;
    }
    *op++ = '-'; *op++ = '1'; *op++ = '\n';
    d->out_size = (unsigned long)(op - d->out);
    return 0;
}

评测结果