[BOJ 20930] 우주 정거장

https://www.acmicpc.net/problem/20930

20930번: 우주 정거장

Tag : dsu, greedy

 

문제요약

이차원 평면 상의 선분이 N개 주어진다. x축 또는 y축과 평행한 방향으로는 마음대로 이동할 수 있을 때

쿼리마다 각 선분을 오갈 수 있는지 구하는 문제다.

 

풀이

x축으로 한번, y축으로 한번 정렬하고 현재 컴포넌트에서 가장 오른쪽인 점 >= 다음 점의 x 중 작은 것일 때 이어주면 된다. 

 

전체코드

#include "bits/stdc++.h"
#define endl '\n'
# pragma GCC optimize ("O3")
# pragma GCC optimize ("Ofast")
# pragma GCC optimize ("unroll-loops")
# pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")

using namespace std;
using ll = long long;

int N, Q;
struct pos{int x1, y1, x2, y2, idx;};
vector<pos> v;

struct DSU{
    vector<int> pa, sz; int n;
    DSU(int _n) : n(_n) { pa.resize(n + 1); sz.resize(n + 1, 1); iota(pa.begin(), pa.end(), 0); }
    int find(int a) { return pa[a] == a ? a : (pa[a] = find(pa[a])); }
    int merge(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return 0;
        if(sz[a] < sz[b]) swap(a, b);
        pa[b] = a;
        sz[a] += sz[b];
        return 1;
    }
};

#include <unistd.h>
#include <sys/stat.h>
#include <sys/mman.h>
int z[36];
char*c=(char*)mmap(0,z[12],1,2,0,fstat(0,(struct stat *)z));
inline int f(){int x=0;bool e;c+=e=*c=='-';while(*c>='0')x=10*x+*c++-'0';c++;return e?-x:x;}
char O[2000000],*d=O;
template<class T> inline void p(T x) {
    if(x<0) *d++='-', x=-x;
    char t[16], *q=t;
    do *q++=x%10|48; while(x/=10);
    do *d++=*--q; while(q!=t);
    *d++=10;
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    
    N = f(); Q = f();
    v.resize(N); int _ = 0;
    for(auto &[a, b, c, d, idx] : v) a = f(), b = f(), c = f(), d = f(), idx = ++_;
    sort(v.begin(), v.end(), [&](pos &a, pos &b)->int{
        return min(a.x1, a.x2) < min(b.x1, b.x2);
    });
    DSU uf(N);
    int e = max(v[0].x1, v[0].x2);
    for(int i=1; i<v.size(); i++) {
        if(min(v[i].x1, v[i].x2) <= e)
            uf.merge(v[i-1].idx, v[i].idx);
        e = max({e, v[i].x1, v[i].x2});
    }
    sort(v.begin(), v.end(), [&](pos &a, pos &b)->int{
        return min(a.y1, a.y2) < min(b.y1, b.y2);
    });
    e = max(v[0].y1, v[0].y2);
    for(int i=1; i<v.size(); i++) {
        if(min(v[i].y1, v[i].y2) <= e)
            uf.merge(v[i-1].idx, v[i].idx);
        e = max({e, v[i].y1, v[i].y2});
    }
    while(Q--) {
        int a = f(), b = f();
        p(uf.find(a) == uf.find(b));
    }
    write(1, O, d - O);
}