Submission #49030472

---

Source Code Expand

/*
Author: cnyz
世界があたしを拒んでも今 愛の唄 歌わせてくれないかな
*/
#include<bits/stdc++.h>
using namespace std;

using db=double;
using ll=long long;
using vi=vector<int>;
using pii=pair<int,int>;
using ull=unsigned long long;

#define fi first
#define se second
#define gc getchar
#define pb emplace_back
#define mkp make_pair
#define push emplace
#define sz(a) (int)a.size()
#define all(p) p.begin(),p.end()
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define ROF(i,a,b) for(int i=a;i>=b;i--)
#define ppc(x) __builtin_popcount(x)
#define clz(x) __builtin_clz(x)

bool Mbe;

void chkmax(int &x,int y) {if(x<y) x=y;}
void chkmin(int &x,int y) {if(x>y) x=y;}
void chkmax(ll &x,ll y) {if(x<y) x=y;}
void chkmin(ll &x,ll y) {if(x>y) x=y;}
int read() { int x; cin>>x; return x; }

const int N=1e5+5;
mt19937 rng(time(0));
vi G[N],G2[N];
int o[N],n;
int dfn[N],low[N],dfc,ct,scc[N],st[N],ins[N],top;
void tarjan(int u) {
    dfn[u]=low[u]=++dfc;
    st[++top]=u,ins[u]=1;
    for(int v:G2[u]) {
        if(!dfn[v]) tarjan(v),chkmin(low[u],low[v]);
        else if(ins[v]) chkmin(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]) {
        ++ct;
        while(st[top]!=u) scc[st[top]]=ct,ins[st[top]]=0,top--;
        scc[u]=ct,ins[u]=0,top--;
    }
}
bool chk() {
    FOR(i,1,2*n) dfn[i]=low[i]=scc[i]=ins[i]=0,G2[i].clear();
    FOR(i,1,n) {
        int a=G[i][0],b=G[i][1],c=G[i][2];
        if(o[i]) {
            G2[a+n].pb(b),G2[a+n].pb(c);
            G2[b+n].pb(a),G2[b+n].pb(c);
            G2[c+n].pb(a),G2[c+n].pb(b);
        }
        else {
            G2[a].pb(b+n),G2[a].pb(c+n);
            G2[b].pb(a+n),G2[b].pb(c+n);
            G2[c].pb(a+n),G2[c].pb(b+n);
        }
    }
    dfc=top=ct=0;
    FOR(i,1,2*n) if(!dfn[i]) tarjan(i);
    FOR(i,1,n) if(scc[i]==scc[i+n]) return 1;
    return 0;
}
void solve() {
    n=read(); int m=n*3/2;
    FOR(i,1,n) G[i].clear();
    FOR(i,1,m) {
        int u=read(),v=read();
        G[u].pb(v),G[v].pb(u);
    }
    while(1) {
        FOR(i,1,n) o[i]=rng()%2;
        if(chk()) break;
    }
    FOR(i,1,n) cout<<(o[i]?'B':'W');
    cout<<"\n";
}

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

Submission Info

Judge Result