2016-2017 ACM-ICPC Pacific Northwest Regional Contest (Div. 1) - F: Illumination ★★★★☆

評価

2-SATに見えない良問.
dfsしてしまいWA, 同値類で分解できるじゃーんと言ってUFしてWAした.

問題

n×nのグリッドのいくつかのマスに照明がある.
照明は全部でL個あり, 照明iは, に配置されている.
各照明は上下または左右に距離Rまで(合計2R+1マス)照らせる.
各照明の方向をうまく決め, 問題のないようにできるか判定せよ.
問題がある ⇔ ある照明の組(照明i, 照明j) ()が存在して, 照明iと照明jが置かれた行または列が等しく, ある同じマスを照らしている
codeforces.com

制約

考察

照明iを横向きに置くなら1, 縦向きに置くなら0
とすると, ならば

• 
• 
• 

なる照明jは縦向きでなければならない
などの制約 がたくさん出てきてこれは2-SAT.

解答

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll,ll> P;

const ll linf = 1e18;

#define FOR(i,a,b) for(ll i = (a); i < (b); ++i)
#define RFOR(i,a,b) for(ll i = (b)-1; i >= (a); --i)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define EACH(i,v) for(auto&& i : v)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back

template<class T>
istream& operator>>(istream& is, vector<T>& v) {
    EACH(i, v) is >> i;
    return is;
}

class UnionFind {
    vector<ll> par, h;
public:
    UnionFind(ll size) {
        par.assign(size, 0);
        h.assign(size, 0);
        REP(i, size) par[i] = i;
    }
    void unite(ll u, ll v) {
        u = root(u), v = root(v);
        if (u == v) return;
        if (h[u] > h[v]) {
            par[v] = u;
        }
        else if (h[u] < h[v]) {
            par[u] = v;
        }
        else {
            ++h[u];
            par[v] = u;
        }
    }
    bool isUnited(ll u, ll v) {
        return root(u) == root(v);
    }
    ll root(ll v) {
        if (par[v] == v) return v;
        return par[v] = root(par[v]);
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n, R, L; cin >> n >> R >> L;
    vector<vector<ll>> m(n, vector<ll>(n, -1));
    vector<P> lumps;
    REP(i, L) {
        ll x, y; cin >> y >> x; --x, --y;
        m[y][x] = i;
        lumps.pb({x, y});
    }
    auto id = [&](ll lid, ll dir) {
        return lid * 2 + dir;
    };
    auto inRange = [&](ll x, ll y) {
        return 0 <= x && x < n && 0 <= y && y < n;
    };
    UnionFind uf(L * 2);
    REP(lid, lumps.size()) {
        P p = lumps[lid];
        // row
        FOR(dx, -2*R, 2*R+1) {
            if (dx == 0) continue;
            ll nx = p.first + dx;
            ll ny = p.second;
            if (!inRange(nx, ny)) continue;
            if (m[ny][nx] < 0) continue;
            ll nlid = m[ny][nx];
            assert(lid != nlid);
            uf.unite(id(lid, 0), id(nlid, 1));
            // cout << "0:" << lid << " " << "1:" << nlid << endl;
        }
        // col
        FOR(dy, -2*R, 2*R+1) {
            if (dy == 0) continue;
            ll nx = p.first;
            ll ny = p.second + dy;
            if (!inRange(nx, ny)) continue;
            if (m[ny][nx] < 0) continue;
            ll nlid = m[ny][nx];
            uf.unite(id(lid, 1), id(nlid, 0));
            // cout << "1:" << lid << " " << "0:" << nlid << endl;
        }
    }
    try {
        REP(i, L) {
            // cout << L*2 << " " << id(i,0) << " " << id(i,1) << endl;
            // cout << uf.isUnited(id(i, 0), id(i, 1)) << endl;
            if ( uf.isUnited(id(i, 0), id(i, 1)) ) throw 1;
        }
        cout << "YES" << endl;
    }
    catch (int err) {
        cout << "NO" << endl;
    }
}