BOJ 2472 - 체인점

문제 태그 : https://www.acmicpc.net/problem/2472

정말 좋은 문제라고 생각한다. 여러가지 테크닉을 같이 써야 문제를 해결할 수 있다. 그런데 최근에 재채점을 당해 틀려서 다시 푼 김에 글을 작성하였다. 

문제 소개

그래프가 주어지고 3개의 출발 지점이 주어진다. 만약 지점 A와 B가 존재해서 출발지점 3곳에 대해서 모두 B가 A보다 출발 지점까지의 거리가 짧으면 A에는 매장을 설치할 수 없다. 각 지점에 대해서 질의를 던지면 그 지점에 매장을 설치할 수 있는지 대답을 해야한다.

문제 풀이

일단 그래프 상에서 어떠한 한 노드를 중심으로 다른 모든 점까지의 거리를 각각 구하는 것은 다익스트라를 3번 돌리는 것으로 쉽게 처리해 줄 수가 있다. 다르게 말하면 우리는 모든 노드에 대해 각 시작점으로부터의 거리 a,b,c를 주었다. 따라서 우리는 $a_i>a_j$ $b_i>b_j$ $c_i>c_j$인 j가 존재하는 모든 i를 찾는 것이 목표이다. 그리고 이 작업은 세그먼트 트리를 재밌게 사용하여 처리해 줄 수 있음이 알려져 있다.

일단 a에 대해서 정렬한다. a가 작은 순서대로 세그트리에 업데이트를 하면, 어떤 지점의 a,b,c를 가지고 볼 때는 이미 자신보다 작은 a들에 대해서는 모두 처리가 되어있을 것이다. 이로써 a를 처리해 주었다.

업데이트는 b의 위치에 할 것이다. 앞의 지점들에 대해서 그 지점들의 b의 위치에 업데이트를 해주었다면 현재의 b'에 대해서는 1~b-1의 구간을 확인하는 것으로 자신보다 b가 작은 지점만 뽑아낼 수 있다.

초기값은 inf이며 업데이트할 값은 c이고, 세그는 구간 최솟값을 관리하는 세그를 사용한다. 따라서 어떤 상황에서 1~b-1 구간을 취하면, 그 지점보다 a값도 작고, b값도 작은 지점들의 c값중 가장 작은 값을 뽑아낼 수 있다. 이 값이 현재 확인하는 지점의 c값보다 작으면 이 지점에는 매장을 설치할 수 없고, 쿼리를 통해 얻은 값이 더 크다면 세 값 모두 작은 지점이 없으므로 현재 위치에 매장을 설치할 수 있다는 것이다.

코드

부등호가 성립안하고 셋 다 "더 작은"이기 때문에 이를 잘 고려해서 깔끔하게 처리를 해주어야 한다. 또한, b의 위치에 업데이트를 하므로 좌표압축처럼 진행을 해주어야 한다. 

※실제 코드에서는 c에 대해서 정렬을 한 후에, a값의 위치에 b값을 업데이트 해주었다. 

#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> pii;
#define ff first 
#define ss second
#define ep emplace
#define eb emplace_back
ll dis[1010101];
vector<pii> edg[101010];
 
void dijk(ll st){
    priority_queue<pii,vector<pii>,greater<pii>> pq;
    dis[st]=0;
    pq.ep(0,st);
    while(!pq.empty()){
        auto x=pq.top(); pq.pop();
        if(dis[x.ss]<x.ff) continue;
        for(auto n : edg[x.ss]){
            if(dis[x.ss]+n.ff<dis[n.ss]){
                dis[n.ss]=dis[x.ss]+n.ff;
                pq.push({dis[n.ss],n.ss});
            }
        }
    }
}
 
struct poi{
    ll idx,aidx,bidx,ans;
};
poi arr[1010101];
 
ll tree[1010101];
 
ll upt(ll idx,ll val,ll s,ll e,ll nod){
    if(idx<s||idx>e) return tree[nod];
    if(s==e) return tree[nod]=min(tree[nod],val);
    return tree[nod]=min(upt(idx,val,s,(s+e)/2,nod*2),upt(idx,val,(s+e)/2+1,e,nod*2+1));
}
 
ll sol(ll l,ll r,ll s,ll e,ll nod){
    if(r<s||e<l) return 1e18;
    if(l<=s&&e<=r) return tree[nod];
    return min(sol(l,r,s,(s+e)/2,nod*2),sol(l,r,(s+e)/2+1,e,nod*2+1));
}
 
bool sf(poi a,poi b){
    return dis[a.idx]<dis[b.idx];
}
bool sf2(poi a,poi b){
    return a.idx<b.idx;
}
int main(){
    ll i,j,k,l,m,n,ast,bst,cst,a,b,c;
    scanf("%lld",&n);
    scanf("%lld %lld %lld",&ast,&bst,&cst);
    scanf("%lld",&m);
    for(i=1;i<=m;i++){
        scanf("%lld %lld %lld",&a,&b,&c);
        edg[a].eb(c,b);
        edg[b].eb(c,a);
    }
    for(i=1;i<=4*n;i++){
        tree[i]=1e18;
        arr[i].idx=i;
    }
 
    dis[0]=-1e18;
    for(i=1;i<=n;i++)
        dis[i]=1e18;
    dijk(ast);
    sort(arr+1,arr+1+n,sf);
    for(i=1;i<=n;i++){
        arr[i].aidx=arr[i-1].aidx;
        if(dis[arr[i].idx]!=dis[arr[i-1].idx]) arr[i].aidx++;
    }
 
    for(i=1;i<=n;i++)
        dis[i]=1e18;
    dijk(bst);
    sort(arr+1,arr+1+n,sf);
    for(i=1;i<=n;i++){
        arr[i].bidx=arr[i-1].bidx;
        if(dis[arr[i].idx]!=dis[arr[i-1].idx]) arr[i].bidx++;
    }
 
    for(i=1;i<=n;i++)
        dis[i]=1e18;
    dijk(cst);
    sort(arr+1,arr+1+n,sf);
    ll fl=1;
    while(fl<=n){
        ll nfl=fl;
        while(dis[arr[fl].idx]==dis[arr[nfl].idx]){
            if(sol(1,arr[nfl].aidx-1,1,n,1)<arr[nfl].bidx) arr[nfl].ans=1;
            nfl++;
        }
        for(i=fl;i<nfl;i++){
            upt(arr[i].aidx,arr[i].bidx,1,n,1);
        }
        fl=nfl;
    }
 
    sort(arr+1,arr+1+n,sf2);
    scanf("%lld",&k);
    for(i=1;i<=k;i++){
        scanf("%lld",&l);
        if(arr[l].ans) printf("NO\n");
        else printf("YES\n");
    }
}