2020 Petrozavodsk Winter Camp, Jagiellonian U Contest J問題 Space Gophers

問題ページ

トンネルが連結なパターンを2通りに分ける

• 並行な場合
  隣接している4パターンのみ考えられる。mapかsetで存在するトンネルを保持しておけばこの判定はできる。
• 垂直な場合
  x軸に垂直なトンネルとy軸に垂直なトンネルが連結となるのはz座標の差が1以下であるときのみである。x軸に垂直でz座標がzのトンネルとx軸に垂直でz座標がz-1,z,zのトンネルを連結にする。連結なトンネルについてすべての集合を持つ必要はないので、トンネルの集合を圧縮する。これをすべてのzについて行う。垂直な方向が違う場合についても対称に同様に計算できる。

#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  
constexpr ll INF = 1LL<<60;  
  
struct UnionFind {  
    vector<ll> par, s;  
    UnionFind(ll n) : par(n), s(n, 1) { iota(ALL(par), 0); }  
    ll find(ll x) {  
        if(par[x] == x) return x;  
        return par[x] = find(par[x]);  
    }  
    void unite(ll x, ll y) {  
        x = find(x), y = find(y);  
        if(x == y) return;  
        if(s[x] < s[y]) par[x] = y, s[y] += s[x];  
        else par[y] = x, s[x] += s[y];  
    }  
    bool same(int x, int y) { return find(x) == find(y); }  
    ll size(int x) { return s[find(x)]; }  
};  
  
void solve() {  
    ll n;  
    cin >> n;  
    vector<ll> x(n), y(n), z(n);  
    map<tuple<ll,ll,ll>, ll> mp;  
    REP(i, n) {  
        cin >> x[i] >> y[i] >> z[i];  
        mp[{x[i], y[i], z[i]}] = i;  
    }  
  
    // 並行で連結な分をつなぐ  
    UnionFind uf(n);  
    REP(i, n) {  
        if(x[i]==-1) {  
            if(mp.find({-1, y[i]-1, z[i]}) != mp.end()) uf.unite(i, mp[{-1, y[i]-1, z[i]}]);  
            if(mp.find({-1, y[i]+1, z[i]}) != mp.end()) uf.unite(i, mp[{-1, y[i]+1, z[i]}]);  
            if(mp.find({-1, y[i], z[i]-1}) != mp.end()) uf.unite(i, mp[{-1, y[i], z[i]-1}]);  
            if(mp.find({-1, y[i], z[i]+1}) != mp.end()) uf.unite(i, mp[{-1, y[i], z[i]+1}]);  
        } else if(y[i]==-1) {  
            if(mp.find({x[i]-1, -1, z[i]}) != mp.end()) uf.unite(i, mp[{x[i]-1, -1, z[i]}]);  
            if(mp.find({x[i]+1, -1, z[i]}) != mp.end()) uf.unite(i, mp[{x[i]+1, -1, z[i]}]);  
            if(mp.find({x[i], -1, z[i]-1}) != mp.end()) uf.unite(i, mp[{x[i], -1, z[i]-1}]);  
            if(mp.find({x[i], -1, z[i]+1}) != mp.end()) uf.unite(i, mp[{x[i], -1, z[i]+1}]);  
        } else {  
            if(mp.find({x[i]-1, y[i], -1}) != mp.end()) uf.unite(i, mp[{x[i]-1, y[i], -1}]);  
            if(mp.find({x[i]+1, y[i], -1}) != mp.end()) uf.unite(i, mp[{x[i]+1, y[i], -1}]);  
            if(mp.find({x[i], y[i]-1, -1}) != mp.end()) uf.unite(i, mp[{x[i], y[i]-1, -1}]);  
            if(mp.find({x[i], y[i]+1, -1}) != mp.end()) uf.unite(i, mp[{x[i], y[i]+1, -1}]);  
        }  
    }  
  
    // 垂直で連結な分をつなぐ  
    {  
        vector<ll> vx, vy, vz;  
        REP(i, n) {  
            if(x[i]==-1) vx.push_back(i);  
            else if(y[i]==-1) vy.push_back(i);  
            else vz.push_back(i);  
        }  
  
        map<ll,vector<ll>> xz, yz, xy, zy, yx, zx;  
        for(auto i: vx) xz[z[i]].push_back(i);  
        for(auto i: vy) yz[z[i]].push_back(i);  
        for(auto i: vx) xy[y[i]].push_back(i);  
        for(auto i: vz) zy[y[i]].push_back(i);  
        for(auto i: vy) yx[x[i]].push_back(i);   
        for(auto i: vz) zx[x[i]].push_back(i);  
  
        auto unite = [&](vector<ll> &a, vector<ll> &b) {  
            if(a.size() && b.size()) {  
                for(auto i: b) uf.unite(a[0], i);  
                for(auto i: a) uf.unite(i, b[0]);  
                a = {uf.find(a[0])};  
                b = {uf.find(b[0])};  
            }  
        };  
  
        // (-1, ya, za) (xb, -1, zb)  
        for(auto i: vx) {  
            if(yz.find(z[i]-1) != yz.end()) unite(xz[z[i]], yz[z[i]-1]);  
            if(yz.find(z[i]) != yz.end()) unite(xz[z[i]], yz[z[i]]);  
            if(yz.find(z[i]+1) != yz.end()) unite(xz[z[i]], yz[z[i]+1]);  
        }  
        // (-1, ya, za) (xb, yb, -1)  
        for(auto i: vx) {  
            if(zy.find(y[i]-1) != zy.end()) unite(xy[y[i]], zy[y[i]-1]);  
            if(zy.find(y[i]) != zy.end()) unite(xy[y[i]], zy[y[i]]);  
            if(zy.find(y[i]+1) != zy.end()) unite(xy[y[i]], zy[y[i]+1]);  
        }  
        // (xa, -1, za) (xb, yb, -1)  
        for(auto i: vy) {  
            if(zx.find(x[i]-1) != zx.end()) unite(yx[x[i]], zx[x[i]-1]);  
            if(zx.find(x[i]) != zx.end()) unite(yx[x[i]], zx[x[i]]);  
            if(zx.find(x[i]+1) != zx.end()) unite(yx[x[i]], zx[x[i]+1]);  
        }  
    }  
  
    map<PII,ll> xy, xz, yz;  
    REP(i, n) {  
        if(x[i]==-1) yz[{y[i], z[i]}] = i;  
        else if(y[i]==-1) xz[{x[i], z[i]}] = i;  
        else xy[{x[i], y[i]}] = i;  
    }  
  
    ll q;  
    cin >> q;  
    REP(i, q) {  
        ll sx, sy, sz, gx, gy, gz;  
        cin >> sx >> sy >> sz >> gx >> gy >> gz;  
  
        ll vs = -1;  
        if(yz.find({sy, sz}) != yz.end()) vs = yz[{sy, sz}];  
        if(xy.find({sx, sy}) != xy.end()) vs = xy[{sx, sy}];  
        if(xz.find({sx, sz}) != xz.end()) vs = xz[{sx, sz}];  
  
        ll vg = -1;  
        if(yz.find({gy, gz}) != yz.end()) vg = yz[{gy, gz}];  
        if(xy.find({gx, gy}) != xy.end()) vg = xy[{gx, gy}];  
        if(xz.find({gx, gz}) != xz.end()) vg = xz[{gx, gz}];  
  
        if(vs!=-1 && vg!=-1 && uf.same(vs, vg)) cout << "YES\n";  
        else cout << "NO\n";  
    }  
}  
  
int main() {  
    ll test;  
    cin >> test;  
    REP(i, test) solve();  
  
    return 0;  
}