Mountaineers (백준 16074)

안녕하세요. 오늘은 산을 오를 거예요.

문제

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

아이디어

크게 두가지 풀이 방법이 있습니다.
첫번째는 MST를 만들어서 경로의 최댓값 LCA를 수행하는 것이고
두번째는 그래프를 다 연결해서 PBS를 수행하는 것입니다.
저는 후자를 택했습니다 (사실 문제 풀기 전까지 첫번째 방법은 상상도 못했습니다).

일단 그래프를 다 잇습니다.
정점의 가중치라는건 없으므로 간선에 가중치를 매깁니다.
그리고 PBS를 돌립니다.
그러면 정답이 나옵니다.

여기서 주의할 점은 두 점이 같을 수도 있다는 것입니다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#define ll long long
using namespace std;

ll N, M, arr[555][555] = { 0 };
ll change(pair <ll, ll> dot)
{
    return (dot.first - 1) * M + dot.second;
}

vector <pair <ll, ll> > connect[1010101];
vector <pair <ll, ll> > qry;
ll Left[101010] = { 0 }, Right[101010] = { 0 }, Ans[101010] = { 0 };
vector <ll> mid[1010101];

ll par[252525] = { 0 };
void init()
{
    for (ll i = 1; i <= 250000; i++) par[i] = i;
    for (ll i = 1; i <= 1000000; i++) mid[i].clear();
}
ll find(ll x)
{
    if (x == par[x]) return x;
    return par[x] = find(par[x]);
}
void Union(ll x, ll y)
{
    par[find(x)] = find(y);
}
bool same(ll x, ll y)
{
    return find(x) == find(y);
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll Q, i, j, x1, y1, x2, y2;

    cin >> N >> M >> Q;
    for (i = 1; i <= N; i++)
        for (j = 1; j <= M; j++)
            cin >> arr[i][j];
    init();
    for (i = 1; i <= N; i++)
    {
        for (j = 1; j <= M; j++)
        {
            if (i != N) connect[max(arr[i][j], arr[i + 1][j])].push_back({ change({i,j}),change({i + 1,j}) });
            if (j != M) connect[max(arr[i][j], arr[i][j + 1])].push_back({ change({i,j}),change({i,j + 1}) });
        }
    }

    for (i = 0; i < Q; i++)
    {
        cin >> x1 >> y1 >> x2 >> y2;
        qry.push_back({ change({x1,y1}),change({x2,y2}) });
        Left[i] = arr[x1][y1];
        Right[i] = 1000001;
    }

    while (true)
    {
        init();
        bool done = true;
        for (ll i = 0; i < Q; i++)
        {
            if (Left[i] < Right[i])
            {
                done = false;
                mid[(Left[i] + Right[i]) / 2].push_back(i);
            }
        }
        if (done) break;

        for (ll i = 1; i <= 1000000; i++)
        {
            for (auto temp : connect[i]) Union(temp.first, temp.second);

            for (ll now : mid[i])
            {
                if (same(qry[now].first, qry[now].second))
                {
                    Ans[now] = i;
                    Right[now] = i;
                }
                else Left[now] = i + 1;
            }
        }
    }

    for (ll i = 0; i < Q; i++)
        cout << Ans[i] << "\n";
}

감사합니다.