백준20445 구간 겹치기

작성일 | In

문제 링크

  • http://icpc.me/20445

사용 알고리즘

  • 플로이드

시간복잡도

  • $O(N^3 + Q)$

풀이

수직선 상의 구간 $[a, b]$를 덮는 것을 $s$번 정점에서 $b$번 정점으로 가는 것이라고 생각해 봅시다. $[s, e]$를 하나의 구간으로 덮는 것은, $s \leq i \leq j \leq e$인 모든 $i, j$에 대해 $i$에서 $j$로 가는 지름길이라고 생각할 수 있습니다.

입력으로는 $[-10^9, 10^9]$까지 주어질 수 있지만, 좌표 압축을 하면 정점의 개수를 $2N$개 이하로 줄일 수 있습니다.
간선은 구간마다 $O(N^2)$개씩 만들어서 총 $O(N^3)$개의 간선을 만들 수도 있고, 아니면 각 정점마다 더미 정점을 하나씩 추가해서 구간마다 $O(N)$개씩 총 $O(N^2)$개의 간선을 만들 수도 있습니다.
아무튼 $O(N)$개의 정점과 $O(N^3)$개 이하의 간선을 만들었다면 Floyd-Warshall algorithm을 이용해 모든 정점 쌍에 대한 정답을 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll N, Q, K, V, A[111], B[111], D[333][333];
vector<ll> C;
inline void AddEdge(int s, int e, ll w){ D[s][e] = min(D[s][e], w); }

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> Q; C.reserve(N+N);
    for(int i=0; i<N; i++) cin >> A[i] >> B[i];
    for(int i=0; i<N; i++) C.push_back(A[i]), C.push_back(B[i]);
    sort(C.begin(), C.end()); C.erase(unique(C.begin(), C.end()), C.end());
    for(int i=0; i<N; i++) A[i] = lower_bound(C.begin(), C.end(), A[i]) - C.begin();
    for(int i=0; i<N; i++) B[i] = lower_bound(C.begin(), C.end(), B[i]) - C.begin();

    K = C.size(); V = N + K;
    memset(D, 0x3f, sizeof D);
    for(int i=0; i<V; i++) AddEdge(i, i, 0);
    for(int i=0; i<N; i++) for(int j=A[i]; j<=B[i]; j++) AddEdge(j, K+i, C[B[i]] - C[A[i]] + 1);
    for(int i=0; i<N; i++) for(int j=A[i]; j<=B[i]; j++) AddEdge(K+i, j, 0);
    for(int k=0; k<V; k++) for(int i=0; i<V; i++) for(int j=0; j<V; j++) D[i][j] = min(D[i][j], D[i][k] + D[k][j]);

    for(int q=1; q<=Q; q++){
        int s, e; cin >> s >> e;
        if(s < C[0] || C.back() < e){ cout << "-1\n"; continue; }
        s = upper_bound(C.begin(), C.end(), s) - C.begin() - 1;
        e = lower_bound(C.begin(), C.end(), e) - C.begin();
        cout << (D[s][e] < 1e18 ? D[s][e] : -1) << "\n";
    }
}