백준 29811 - 지각하기 싫어 (C++)

문제

• 문제 링크

  
   BOJ 29811 - 지각하기 싫어 
  

• 문제 요약

애지문부터 대운동장까지 가는 경로 $N$개, 대운동장부터 ITBT관까지 가는 경로 $M$개가 주어진다.
아래의 쿼리를 수행하는 프로그램을 작성해보자.



$U$ $x$ $y$ : $x$번 경로의 인구를 $y$로 바꾼다.

$L$ : 애지문에서 ITBT관까지 가는 가장 빠른 경로가 $a, b$번 경로를 통해 이동할 때일 때, $a, b$를 출력한다.

• 제한

TL : $1$ sec, ML : $1024$ MB




$1 ≤ N, M ≤ 100,000$

$1 ≤ Q ≤ 200,000$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리를 사용한 집합과 맵 (tree _ set / map)

풀이

먼저 주어지는 $N$개의 경로를 관리할 집합과, 나중에 주어지는 $M$개의 경로를 관리할 집합을 두자.
이때 요소는 {인구수, 경로 번호} 의 형태로 저장한다.

도로의 번호를 식별해야 하므로, 각 번호에 따른 인구수도 매칭해두자.

첫 번째 쿼리가 주어질 경우

$x$가 어느 집합에 속한지 판별한다.

해당 집합에서 우선 $x$를 제거한다.

$x$에 적혀 있던 인구수를 $y$로 업데이트함과 동시에, 집합에 추가한다.

두 번째 쿼리가 주어질 경우

두 개의 집합에서, 맨 위에 있는 두 요소가 곧 $a, b$가 된다.

따라서 쿼리당 $O(log(max(N, M)))$의 복잡도로 문제를 풀 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m; cin >> n >> m;
 
    set <pair<int, int>> NS, MS;
    vector <int> rec(n + m + 1);
    for (int i(1); i <= n + m; i++)
    {
        int x; cin >> x;
        rec[i] = x;
        (i > n ? MS : NS).insert({ x, i });
    }
 
    int q; cin >> q;
    while (q--)
    {
        char op; cin >> op;
        if (op == 'U')
        {
            int x, y; cin >> x >> y;
            auto& S(x > n ? MS : NS);
 
            S.erase({ rec[x], x });
            S.insert({ rec[x] = y, x });
        }
        else
            cout << (*NS.begin()).second << ' ' << (*MS.begin()).second << '\n';
    }
}

comment

끝