Educational codeforces #78 D - Segment Tree (라인스위핑)
https://codeforces.com/contest/1278/problem/D 풀이가 너무 생소해서 정리해둠 최대 5e5개의 정점이 입력된다. 정점은 [l,r]의 정보를 담고 있다. 서로 교차되는(intersect) 정점들이 서로 이어져있다고 할 때, 그 그래프가 트리인지 아닌지를 출력하는 문제. ex) 정점[1,3]과 [2,4]는 이어져있다. 하지만 [1,2],[3,4]는 이어져 있지 않다. +모든 끝점은 유일하다. 예를들어 [1,2][2,3]이 동시에 주어지는 경우는 없다 1. 각 정점의 정보를 P a[MAX]에 담아둔다. 2. vector evs에 (a[i].first, i) 와 (a[i].second, i)를 모두 담아서 오름차순 정렬한다. 3. set cand를 마련한다. (아직 교차할 정점..
2019. 12. 29.
CSES PS - Grid Paths
https://cses.fi/problemset/task/1625/ 백트래킹 문제. 아이디어가 안떠올라서 답확인함. 7*7 공간에서 (0,0) ~ (6,0)까지 갈 때 경로가 ?,L,R,U,D 총 48자로 주어진다. 이때 ?대신 아무 방향이나 사용할 수 있을 때 가능한 경로의 수를 모두 구하는 문제. ?가 48개 있을 때 백트래킹 없이 dfs하면 4^48만큼의 시간이 걸리므로 백트래킹이라고 생각하지 않았다. U 9개 D 15개, R 12개, L 12개의 적절한 순열인 줄 알았지만 아니었다. (빨간색은 방문할 수 없는 지점(벽너머거나, 방문했거나), 파란색은 방문할 수 있는 지점(y>0 && y 0 && cy < 6 && !visited[cy - 1][cx] && !visited[cy + 1][cx]) r..
2019. 12. 22.
