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; } }