Submission #41814075

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned long long;

// mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937 rnd(0);
int rd(int l, int r) {return rnd() % (r - l + 1);}

constexpr int mod = 998244353;
void addt(int &x, int y) {x += y, x >= mod && (x -= mod);}
int add(int x, int y) {return x += y, x >= mod && (x -= mod), x;}
int ksm(int a, int b) {
  int s = 1;
  while(b) {
    if(b & 1) s = 1ll * s * a % mod;
    a = 1ll * a * a % mod, b >>= 1;
  }
  return s;
}

constexpr int Z = 1e5 + 5;
int fc[Z], ifc[Z];
int bin(int n, int m) {
  if(n < m) return 0;
  return 1ll * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
void init_fac(int Z) {
  for(int i = fc[0] = 1; i < Z; i++) fc[i] = 1ll * fc[i - 1] * i % mod;
  ifc[Z - 1] = ksm(fc[Z - 1], mod - 2);
  for(int i = Z - 2; ~i; i--) ifc[i] = 1ll * ifc[i + 1] * (i + 1) % mod;
}

bool Mbe;
constexpr int N = 1e5 + 5;
constexpr int M = N * 6 + 5;

int n, f[N];
vector<int> e[N];
int cnt, hd[N], nxt[M], to[M];
void adde(int u, int v) {
  nxt[++cnt] = hd[u], hd[u] = cnt, to[cnt] = v;
}

int dfn[N], low[N], dn, stc[N], top, vis[N], col[N], cn;
void tarjan(int id) {
  dfn[id] = low[id] = ++dn;
  stc[++top] = id, vis[id] = 1;
  for(int i = hd[id]; i; i = nxt[i]) {
    int it = to[i];
    if(!dfn[it]) {
      tarjan(it);
      low[id] = min(low[id], low[it]);
    }
    else if(vis[it]) low[id] = min(low[id], dfn[it]);
  }
  if(dfn[id] == low[id]) {
    cn++;
    for(int x = 0; x != id; ) {
      x = stc[top--];
      vis[x] = 0, col[x] = cn;
    }
  }
}

void solve() {
  cin >> n;
  for(int i = 1; i <= n; i++) e[i].clear();
  for(int i = 1; i <= n * 3 / 2; i++) {
    int a, b;
    cin >> a >> b;
    e[a].push_back(b);
    e[b].push_back(a);
  }
  while(1) {
    for(int i = 1; i <= n; i++) f[i] = rnd() & 1;
    memset(hd, 0, N << 2), cnt = 0;
    for(int i = 1; i <= n; i++) {
      int u = e[i][0], v = e[i][1], w = e[i][2];
      if(f[i]) {
        adde(u, v + n);
        adde(u, w + n);
        adde(v, u + n);
        adde(v, w + n);
        adde(w, u + n);
        adde(w, v + n);
      }
      else {
        adde(u + n, v);
        adde(u + n, w);
        adde(v + n, u);
        adde(v + n, w);
        adde(w + n, u);
        adde(w + n, v);
      }
    }
    memset(dfn, 0, N << 2), dn = cn = 0;
    for(int i = 1; i <= n + n; i++) if(!dfn[i]) tarjan(i);
    for(int i = 1; i <= n; i++) {
      if(col[i] != col[i + n]) continue;
      for(int j = 1; j <= n; j++) cout << (f[j] ? 'B' : 'W');
      cout << "\n";
      return;
    }
  }
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int T = 1;
  cin >> T;
  while(T--) solve();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}

Submission Info

Judge Result