BOJ 5542 - JOI 국가의 행사

문제 링크 : https://www.acmicpc.net/problem/5542

문제 풀이

 이 문제에서 쿼리 q개를 제거해보자. 그러면 어떻게 풀 수 있을까? 이 형태의 문제를 해결하기 위해서 생각해야 하는 핵심 아이디어는 바로 결정 문제로 바꾸어서 해결하는 것이다. 목적지까지 이동하는 도중 축제랑 가장 멀리 떨어질 수 있는 거리 x 를 구하는 것은, 축제랑 거리 x이상 떨어진 노드들만 사용해서 목적지까지 이동이 가능한지를 묻는 결정 문제로 바꿔서 생각할 수 있다. 

 결정 문제는 어떻게 해결할까? 일단 각 노드들이 축제로부터 거리가 얼마나 떨어져 있는지를 알아야 하기 때문에 다익스트라를 먼저 실시해야 한다. 모든 축제 정점은 거리 0으로 해놓고 pq에 넣은 후에 시작하면 모든 노드에 대해서 가장 가까운 축제까지의 거리를 알 수 있다. 
 이후 x이상인 노드들끼리 연결하는 간선이 존재하면 간선의 양 끝 두 노드를 merge 한 후에, 시작점과 도착점이 같은 그룹에 속해있는 지를 확인하는 것으로 질문에 대한 답을 할 수 있다. 하지만 한 x에 대해서 최대 시간복잡도가 O(M) 이 걸리기 때문에 모든 x에 대해서 마구잡이로 하면 안되고, x값이 작아질 수록 노드들이 추가되기만 한다는 점을 이용해서 x를 최대치부터 내려가면서 새로 가능해진 정점들에 대해서만 확인하고 merge 해주면 O(N+M) 만에 모든 x에 대해서 확인해 줄 수 있다. 

 다시 원래 문제로 돌아가보자. 모든 쿼리에 대해서 위와 같이 행동한다면 O(Q(N+M)) 이 될 것이다. 여기서 우리는 결정문제의 친구인 이분 탐색을 이용하려고 한다. 하지만 여기서는 한번에 모든 쿼리에 대해서 이분탐색을 실시하는 병렬 이분 탐색을 실시한다. 병렬 이분 탐색을 실시하면 한 번 x가 n에서 0까지 내려갈 때마다 모든의 쿼리에 대한 답의 범위가 각각 절반으로 줄어들기 때문에 O((N+M+Q)lgN) 에 답을 구할 수 있다. 전체 시간 복잡도는 다익스트라 까지 포함되어야 하지만, 시간제한 내에는 충분히 문제를 해결할 수 있다. 

Thinking flow

 만약 pbs(parallel binary search, 병렬 이분 탐색) 에 익숙하다면 이 문제는 정말 쉽게 pbs를 사용한다는 것을 알아챌 수 있다. 
1. 그래프 내에서 기준에 따라서 사용할 수 있는 노드(간선) 이 순차적으로 변화함
2. 쿼리 Q개가 기준의 최대치(최소치) 를 물어보고 있음
이 두 가지의 상황에서 빠르게 pbs라는 것을 눈치채고 문제를 해결 할 수 있다. 

해결 코드

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef double dl;
typedef pair<dl,dl> pdi;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> piii;
 
#define ff first
#define ss second
#define eb emplace_back
#define ep emplace
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
#define IDX(v, x) lower_bound(all(v), x) - v.begin()
//cout<<fixed;
//cout.precision(12);
 
struct qr{
    ll s,e,a,b;
};
 
vector<ll> x;
ll n,m;
ll mod=998244353;
string s;
string t;
ll arr[210101];
ll ans[210101];
ll par[210101];
ll dis[210101];
qr qrs[210101];
ll chk[210101];
 
vector<ll> nd[210101];
vector<pii> v[210101];
vector<ll> qq[210101];
priority_queue<pii,vector<pii>,greater<pii>> pq;
 
ll fi(ll x){
    if(par[x]==x) return x;
    return par[x]=fi(par[x]);
}
 
void mer(ll a,ll b){
    a=fi(a);
    b=fi(b);
    if(chk[a]+chk[b]!=2) return;
    par[a]=b;
}
 
void dijk(){
    while(!pq.empty()){
        auto x =pq.top(); pq.pop();
        if(dis[x.ss]<x.ff) continue;
        for(auto nx : v[x.ss]){
            if(dis[x.ss]+nx.ff<dis[nx.ss]){
                dis[nx.ss] = dis[x.ss]+nx.ff;
                pq.emplace(dis[nx.ss],nx.ss);
            }
        }
    }
}
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    ll i,j,k,a,b,c,d,e,f,q;
 
    cin>>n>>m>>k>>q;
 
    for(i=1;i<=m;i++){
        cin>>a>>b>>c;
        v[a].pb({c,b});
        v[b].pb({c,a});
    }
    for(i=1;i<=n;i++){
        dis[i]=1e9+7;
    }
    for(i=1;i<=k;i++){
        cin>>a;
        dis[a]=0;
        pq.push({0,a});
    }
 
    dijk();
    x.pb(-1);
    for(i=1;i<=n;i++){
        //cout<<i<<' '<<dis[i]<<'\n';
        x.pb(dis[i]);
    }
    compress(x);
    ll sz=x.size();
    for(i=1;i<=n;i++){
        ll p=lower_bound(x.begin(), x.end(),dis[i])-x.begin();
        nd[p].pb(i);
    }
    
 
    for(i=1;i<=q;i++){
        cin>>qrs[i].a>>qrs[i].b;
        qrs[i].s=0;
        qrs[i].e=sz;
        ll m=(qrs[i].s+qrs[i].e)/2;
        qq[m].pb(i);
    }
 
    for(ll r=1;r<=20;r++){
        for(i=1;i<=n;i++){
            chk[i]=0;
            par[i]=i;
        }
 
        for(i=sz-1;i>=1;i--){
            for(auto x:nd[i]){
                chk[x]=1;
                for(auto k:v[x]){
                    mer(x,k.ss);
                }
            }
 
            for(auto k:qq[i]){
                if(fi(qrs[k].a)==fi(qrs[k].b)){
                    ans[k]=max(ans[k],i);
                    qrs[k].s=i+1;
                }
                else qrs[k].e=i-1;
            }
            qq[i].clear();
        }
 
        for(i=1;i<=q;i++){
            if(qrs[i].s<=qrs[i].e){
                ll m=(qrs[i].s+qrs[i].e)/2;
                qq[m].pb(i);
            }
        }
    }
 
    for(i=1;i<=q;i++){
        cout<<max(x[ans[i]],0LL)<<'\n';
    }
}