백준 8812 - Jaś Robaczek (C++)

문제

• 문제 링크

  
   BOJ 8812 - Jaś Robaczek 
  

• 문제 요약

최초 $1$개의 노드만이 존재하는 상태에서, 아래 두 쿼리를 수행하는 프로그램을 작성하자.



$D x$ : $x$번 노드에 새로운 노드를 연결한다. 단, $x$는 이미 존재하는 노드임이 보장된다.

$J x$ : Jaś가 $x$번 노드를 향해 한 번 이동한다. 단, 최초 Jaś가 서있는 노드는 $1$번 노드이다.




• 제한

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




$1 ≤$ 테스트 케이스의 수 $≤ 10$

$1 ≤ Q ≤ 10^6$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• 최소 공통 조상 (lowest common ancestor)
• 희소 배열 (sparse_table)
• 오프라인 쿼리 (offline_queries)

풀이

현재 Jaś가 있는 노드를 $now$라 하고, $x$를 향해 이동한다고 하자.

이를 크게 보면, $now$에서 부모 노드를 향해 한 번 이동하거나 직속 자식 노드를 향해 한 번 이동하거나 둘 중 하나이다.

• $LCA(now, x) ≠ now$ 라면, $now$에서 반드시 부모 정점으로 이동해야 한다.
• $LCA(now, x) == now$ 라면, $now$에서 $x$로 향하는 가장 처음 자식 노드로 이동해야 한다.
  • 이 노드는 $x$를 $dep[x] - dep[now] - 1$만큼 끌어올린 정점과 같다.

쿼리를 모두 받아놓고, 최종 트리의 모양을 알아낸 뒤 $LCA$를 위한 전처리를 진행하자.
다시 쿼리들을 순회하며 $now = 1$을 시작으로 두 번째 쿼리마다 시뮬레이션을 돌려주면 되겠다.

전체 코드

#include<bits/stdc++.h>
#define N 1000001
using namespace std;
 
vector <int> Gr[N];
int n(1), dep[N], dp[N][20];
 
void clear()
{
    for (int i{}; i <= n; Gr[i++].clear());
    memset(dep, 0, sizeof dep);
    memset(dp, 0, sizeof dp);
    n = 1;
}
void LCAInit(int now, int depth)
{
    dep[now] = depth;
    for (int& next : Gr[now])
        if (!dep[next])
        {
            dp[next][0] = now;
            LCAInit(next, depth + 1);
        }
}
void TableDP()
{
    for (int j(1); j < 20; j++)
        for (int i(1); i <= n; i++)
            dp[i][j] = dp[dp[i][j - 1]][j - 1];
}
int Lifting(int x, int diff)
{
    for (int i{}; diff > 0; diff >>= 1, i++)
        if (diff & 1)
            x = dp[x][i];
    return x;
}
int GetLCA(int x, int y)
{
    if (dep[x] < dep[y]) swap(x, y);
 
    x = Lifting(x, dep[x] - dep[y]);
    if (x ^ y)
    {
        for (int i(19); !!~i; i--)
            if (dp[x][i] ^ dp[y][i])
            {
                x = dp[x][i];
                y = dp[y][i];
            }
        x = dp[x][0];
    }
    return x;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    while (t--)
    {
        int q; cin >> q;
 
        vector <pair<char, int>> Q(q);
        for (auto& [op, x] : Q)
        {
            cin >> op >> x;
            if (op == 'D')
                Gr[x].push_back(++n);
        }
 
        LCAInit(1, 1);
        TableDP();
 
        int now(1);
        for (auto& [op, x] : Q)
            if (op == 'J')
            {
                int lca(GetLCA(now, x));
                if (lca == now)
                    cout << (now = Lifting(x, dep[x] - dep[now] - 1)) << '\n';
                else
                    cout << (now = dp[now][0]) << '\n';
            }
 
        clear();
    }
}

comment

끝