BOJ17619: 개구리 점프

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

  • 스위핑이 참 어렵다.
  • Union find로 꾸역꾸역 풀었는데, 매우 비효율적인 구현이었음.
  • 포인트는 끊어진 지점을 찾아서 그룹을 구분해주는것.
  • 다시 풀었음 결국 ㅠㅠ.
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
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

struct Wood {
  int l, r, x;
  bool operator<(const Wood &b) const {
    return l < b.l;
  }
};

class FlogJump {
  int N, M;
  vector<Wood> woods;
  vector<int> group;
public:
  void input();
  void sweep();
  void answerQueries();
};

void FlogJump::input() {
  scanf("%d %d", &N, &M);
  woods.resize(N);
  group.resize(N);
  for(int i = 0; i < N; i++) {
    int l, r, y;
    scanf("%d%d%d", &l, &r, &y);
    woods[i] = {l, r, i};
  }
  sort(woods.begin(), woods.end());
}

struct Node {
  int r, i;
  bool operator<(const Node& b) const {
    return r < b.r;
  }
};

void FlogJump::sweep() {
  int gCnt = 0, maxR = -1;
  for(int i = 0; i < N; i++) {
    auto [l, r, a] = woods[i];
    if(maxR < l) group[a] = ++gCnt;
    else group[a] = gCnt;
    maxR = max(maxR, r);
  }
}

void FlogJump::answerQueries() {
  for(int i = 0; i < M; i++) {
    int a, b;
    scanf("%d%d", &a, &b);
    printf("%d\n", group[a-1] == group[b-1]);
  }
}

int main() {
  FlogJump fj;
  fj.input();
  fj.sweep();
  fj.answerQueries();
}