キーエンス プログラミング コンテスト 2020 E - Bichromization

問題ページ

最小の重み を持つ頂点 について考えてみます．この頂点が隣接する頂点 が より大きい重みしか持たないとします．このとき， を違う色で塗ることは明らかに不可能です．同じ色で塗る場合，別の隣接する頂点へ進む経路で を達成する必要がありますが，隣接する頂点の重みについて条件を達成しようと思うと，重み についての条件が達成できないので不可能です．

したがって，両端点の頂点の重みが一致するような辺が存在しなければ不可能なことがわかりました．両端点の頂点の重みが一致する辺について，頂点の色を異なるように塗り，その重みの辺とすることで，その頂点についての条件は達成できます．

条件を達成できた頂点に隣接する頂点について，重みがより大きいならば，別の色で塗ってその辺の重みを使って条件を達成できます．両端点の頂点の重みが一致する辺の端点からスタートする多点bfsで，より重みが大きい方へ進み，色を塗っていく遷移を行うと，明らかに条件を満たす塗り方です．

コンテスト中は反例見つからなかったので，どうせ十分条件だろうと思って投げたら通った．最小の重みの頂点に限らず，隣接する頂点の重みがその頂点の重みより全て大きいような頂点が存在するならば，不可能な塗り方なことが示せるので，十分条件にもなっていることがわかります．

#include <bits/stdc++.h>  
using namespace std;  
using ll = long long;  
using PII = pair<ll, ll>;  
#define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i)  
#define REP(i, n) FOR(i, 0, n)  
#define ALL(x) x.begin(), x.end()  
template<typename T> void chmin(T &a, const T &b) { a = min(a, b); }  
template<typename T> void chmax(T &a, const T &b) { a = max(a, b); }  
struct FastIO {FastIO() { cin.tie(0); ios::sync_with_stdio(0); }}fastiofastio;  
#ifdef DEBUG_   
#include "../program_contest_library/memo/dump.hpp"  
#else  
#define dump(...)  
#endif  
const ll INF = 1LL<<60;  
  
int main(void) {  
    ll n, m;  
    cin >> n >> m;  
    vector<ll> a(n);  
    REP(i, n) cin >> a[i];  
    vector<ll> col(n);  
    vector<ll> ans(m, 1000000000);  
    vector<vector<PII>> g(n);  
    queue<ll> que;  
    REP(i, m) {  
        ll u, v;  
        cin >> u >> v;  
        u--, v--;  
        g[u].push_back({v, i});  
        g[v].push_back({u, i});  
        if(a[u] == a[v]) {  
            if(col[u] == 0 && col[v] == 0) {  
                col[u] = -1;  
                col[v] = 1;  
                que.push(u);  
                que.push(v);  
                ans[i] = a[u];  
            } else if(col[u] == 0) {  
                col[u] = -col[v];  
                que.push(u);  
                ans[i] = a[u];  
            } else if(col[v] == 0) {  
                col[v] = -col[u];  
                que.push(v);  
                ans[i] = a[u];  
            } else {  
                ans[i] = a[u];  
            }  
        }  
    }  
  
    while(que.size()) {  
        ll v = que.front(); que.pop();  
        for(auto to: g[v]) {  
            if(col[to.first] != 0) continue;  
            if(a[to.first] < a[v]) continue;  
            col[to.first] = -col[v];  
            ans[to.second] = a[to.first];  
            que.push(to.first);  
        }  
    }  
  
    bool flag = true;  
    REP(i, n) {  
        if(col[i] == 0) flag = false;  
    }  
  
    if(!flag) cout << -1 << endl;  
    else {  
        REP(i, n) cout << (col[i]==-1?'W':'B');  
        cout << "\n";  
        REP(i, m) cout << ans[i] << "\n";  
        cout << flush;  
    }  
  
    return 0;  
}