백준 23006 - Truck Delivery (C++)

문제

• 문제 링크

  
   BOJ 23006 - Truck Delivery 
  

• 문제 요약

$N$개의 노드로 이루어진 트리가 주어진다.
각 간선들에는 하중 제한 $Li$, $Li$보다 무거운 화물이 지나갈 경우 부과하는 요금 $A_i$가 있다.
이때, 아래의 쿼리를 수행하는 프로그램을 작성하자.



$C$ $W$ : $C$번 노드에서 $W$의 무게를 가진 화물을 $1$번 노드에 전달한다. 해당 날에 지불하는 요금을 $a_1, a_2, ... a_k$라 할 때 $gcd(a_1, a_2, ... a_k)$의 값을 출력한다.

• 제한

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




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

$2 ≤ C_j ≤ N ≤ 5 * 10^4$

$1 ≤ L_i, W_j ≤ 2 * 10^5$

$1 ≤ Q ≤ 10^5$

알고리즘 분류

• 자료 구조 (data_structures)
• 트리 (trees)
• 수학 (math)
• heavy-light 분할 (heavy-light decomposition)
• 세그먼트 트리 (segment tree)
• 머지 소트 트리 (merge_sort tree)
• 정수론 (number_theory)
• 유클리드 호제법 (euclidean)

풀이

문제의 요구 사항을 이해하자마자 머지 소트 트리가 바로 떠올라서 이를 구현했다.

어떤 구간에 대해, 해당 구간에 속한 {$l_i, a_i$}들을 정렬된 채로 갖고 있고$(mst[])$, 역방향 누적 $gcd$배열$(gcdt[])$을 갖고 있으면 될 것이라고 생각한 것이다.

구체적으로 어떤 구간 $[s, e]$에 속한 $i$에 대해,
$gcdt[i] = gcd(a_i, a_{i+1}, a_{i+2}, ... , a_e)$ 가 되도록 전처리를 하면 된다고 생각했다.(역방향)

그럼 어떤 $W_i$보다 크거나 같은 $l_i$의 인덱스를 $mst[]$에서 이분 탐색으로 $O(logN)$에 찾고, $W_i$보다 크거나 같은 요소들의 $gcd()$를 $gcdt[]$를 이용해 $O(1)$에 구할 수 있게 된다.

아래 코드는 이것들을 착실히 구현한 것이다.

---

오늘의 첫 번째 오버킬 : 오프라인상에서 풀 것을 고민하면 머지 소트 트리는 전혀 필요하지 않다.

오늘의 두 번째 오버킬 : 쿼리의 한 쪽 끝은 $1$로 고정이기 때문에, $hld$까지 필요하지 않다.

결론 : $AC$면 장땡이라고 합리화.

전체 코드

#include<bits/stdc++.h>
#define ll long long
#define N 50001
using namespace std;
 
vector <tuple<int, int, ll>> edge[N];
vector <int> tree[N];
 
vector <pair<int, ll>> mst[1 << 17];
vector <ll> gcdt[1 << 17], recA(N);
 
int top[N], dep[N], par[N], sz[N], in[N];
int n, q, cur, recL[N];
 
void clear()
{
    for (int i{}; i < (1 << 17); mst[i++].clear());
    for (int i{}; i < N; i++)
    {
        sz[i] = in[i] = 0;
        edge[i].clear();
        tree[i].clear();
    }
}
void Input()
{
    cin >> n >> q; cur = 0;
    for (int i{}; ++i < n;)
    {
        ll u, v, l, a; cin >> u >> v >> l >> a;
        edge[u].emplace_back(v, l, a);
        edge[v].emplace_back(u, l, a);
    }
}
void hldDFS1(int now)
{
    sz[now] = 1;
    for (auto& [next, l, a] : edge[now])
        if (!sz[next])
        {
            recL[next] = l;
            recA[next] = a;
            hldDFS1(next);
            sz[now] += sz[next];
            tree[now].push_back(next);
 
            if (sz[next] > sz[tree[now][0]]) swap(tree[now][0], tree[now].back());
        }
}
void hldDFS2(int now)
{
    in[now] = ++cur;
    for (int& next : tree[now])
    {
        top[next] = next ^ tree[now][0] ? next : top[now];
        dep[next] = dep[now] + 1;
        par[next] = now;
        hldDFS2(next);
    }
}
void segUpdate(int n, int s, int e, int i, int l, ll a)
{
    if (s > i || e < i) return;
    mst[n].emplace_back(l, a);
    if (s ^ e)
    {
        int m(s + e >> 1);
        segUpdate(n << 1, s, m, i, l, a);
        segUpdate(n << 1 | 1, m + 1, e, i, l, a);
    }
}
ll segQuery(int n, int s, int e, int l, int r, int w)
{
    if (s > r || e < l) return 0;
    if (s >= l && e <= r)
    {
        int idx(lower_bound(mst[n].begin(), mst[n].end(), pair{ w, 0LL }) - mst[n].begin());
        idx -= idx == mst[n].size() || mst[n][idx].first > w;
        return !~idx ? 0 : gcdt[n][idx];
    }
    int m(s + e >> 1);
    return gcd(segQuery(n << 1, s, m, l, r, w), segQuery(n << 1 | 1, m + 1, e, l, r, w));
}
void segInit()
{
    for (int i(1); i <= n; i++)
        segUpdate(1, 1, n, in[i], recL[i], recA[i]);
    for (int i{}; i < (1 << 17); i++)
        if (mst[i].size())
        {
            sort(mst[i].begin(), mst[i].end());
            gcdt[i].resize(mst[i].size());
            gcdt[i][0] = mst[i][0].second;
            for (int j(1); j < mst[i].size(); j++)
                gcdt[i][j] = gcd(gcdt[i][j - 1], mst[i][j].second);
        }
}
ll hldQuery(int x, int w, ll res = 0)
{
    while (top[x])
    {
        res = gcd(res, segQuery(1, 1, n, in[top[x]], in[x], w));
        x = par[top[x]];
    }
    return gcd(res, segQuery(1, 1, n, 2, in[x], w));
}
void Query(int i)
{
    cout << "Case #" << i << ": ";
    for (int c, w; q--;)
    {
        cin >> c >> w;
        cout << hldQuery(c, w) << ' ';
    }
    cout << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t; cin >> t;
    for (int tc{}; tc++ < t;)
    {
        Input();
        hldDFS1(1);
        hldDFS2(1);
        segInit();
        Query(tc);
        clear();
    }
}

comment

끝