IOI 2018 5번 Highway Tolls 풀이

https://oj.uz/problem/view/IOI18_highway

문제 보기 - 통행료 (IOI18_highway) :: oj.uz

 

모든 서브태스크에서, 도시가 모두 한산할 때의 통행료를 $w_0$이라고 한다. 이것은 1개의 쿼리를 소모해 미리 구해놓는다.

 

1. 5점 풀이(Subtask 1)

쿼리가 100개, 도로가 99개이므로 모든 도로에 대해 그 도로만 혼잡하게 한 다음 통행료 $w$를 계산하면 $w > w_0$인 도로들이 경로를 만들게 된다. 이 경로의 양 끝 점에 있는 두 도시가 $S$와 $T$가 된다.

 

2. 12점 풀이(Subtask 1, 2)

트리상에서 두 도시 $S$와 $T$의 거리는 $D = \frac{w_0}{A}$이다. 도시 0과의 거리가 $D$인 도시들에 대해서 이분탐색을 한다. 각 도시에 대해 그 도시와 연결된 모든 도로를 혼잡하게 만들어도 다른 도시들에게는 영향을 주지 않으므로 이분탐색이 가능하다.

 

3. 6점 풀이(Subtask 3)

주어지는 그래프는 직선이다. 0에 가까운 도시와 $N$에 가까운 도시를 각각 이분탐색 한 번으로 구할 수 있다. 한쪽 끝부터 도로들을 혼잡하게 만들었을 때, 통행료가 $w_0$과 같았다가 커지는 도로를 찾으면 된다.

 

4. 51점 풀이(Subtask 1, 2, 3, 4)

도시에 대해 이분탐색을 진행한다. 몇 개의 도시를 고르고 그 도시와 연결된 도로를 모두 혼잡하게 만든 뒤 통행료가 커졌다면, 고른 몇 개의 도시 중 하나는 $S$ 또는 $T$이다. 이렇게 하면 수많은 반례가 존재한다. 이분탐색으로 찾는 도시는 $S$나 $T$가 아닌 $S$와 $T$ 사이의 도시가 될 수도 있기 때문이다. Subtask 3에서 양 끝점을 구할 수 있던 이유를 생각해보자. $S$와 $T$가 경로상에서 0과 가장 가까운 점이거나 $N$과 가장 가까운 점이기 때문에 이분탐색이 성립했다.

 

따라서 트리에서도 이분탐색을 가능하게 하려면, 도시들의 순서를 다음 조건을 만족할 수 있도록 잘 골라줘야 한다.

 

$S$와 $T$를 잇는 경로상의 도시 중 가장 먼저 등장하는 도시는 $S$ 또는 $T$이다.

 

bfs를 돌면서 방문하는 순서대로 번호를 매겨주고, 이 번호를 뒤집어버리자.(이 순서를 reversed bfs order, 루트 $r$에 대한 RBO라고 부르겠다) $S$와 $T$를 잇는 경로에서 $S$보다 깊은 점이 없거나 $T$보다 깊은 점이 없다. 따라서 0에 대한 RBO로 정점들에 대한 이분탐색을 해주면 양 끝 점 중 하나 $S$를 찾을 수 있다. 이제 루트를 $S$로 바꿔보면, $T$가 경로 상의 도시들 중 가장 깊은 도시가 되므로, S에 대한 RBO로 이분탐색을 다시 돌려주자.

 

5. 90점 풀이(Subtask 1, 2, 3, 4, 5, 6)

 

그래프에서는 $S$와 $T$를 잇는 가장 짧은 경로(여러 개 존재할 수 있다)에 속한 도시가 $S$와 $T$보다 깊어질 수 있다. 따라서 Subtask 4의 풀이를 적용할 수 없다. 도시들을 아무 순서대로 놓고 이분탐색을 한 번 진행하면 찾는 점은 $S$ 또는 $T$가 아닌 $S$와 $T$를 잇는 가장 짧은 경로의 어느 점이 될 수 있다.

 

하지만, $S$와 $T$ 사이의 존재하는 한 점을 알고 있다면? 그 도시를 $A$라고 하자. $A$를 기준으로 bfs tree를 만들면 subtask 4의 풀이를 적용해줄 수 있다. $A$에 대한 RBO로 이분탐색을 돌려 $S$를 찾고, $S$에 대한 RBO로 이분탐색을 돌려 $T$를 찾아주면 된다. 다른 최단경로가 있는지 없는지는 중요하지 않다. 다른 최단경로가 존재하는지 여부는 중요하지 않은데, 어차피 $S$ 주변의 도시를 혼잡하게 만들면 항상 통행료가 증가한다. 이때 $w_0$을 찾을 때 쿼리 1개, $A$, $S$, $T$를 찾을 때 쿼리 17개씩을 사용하므로 쿼리를 총 52개 사용해서 90점을 받을 수 있다. 쿼리 개수를 줄일 수 있는 갖가지 방법을 다 적용해서 쿼리 개수를 쥐어짜면 100점을 받을 수 있다. 반례가 있는지 없는지는 잘 모르겠다. 내 생각에는 반례가 없는 일종의 Case Work인 것 같다.

 

하지만 너무 추하니까 다른 풀이를 알아보자.

 

6. 100점 풀이(Subtask 1, 2, 3, 4, 5, 6)

 

Subtask 5에서 조금만 바꾸면 된다. 경로 상의 한 도시 $A$를 찾는 게 아니라 경로 상에서 연속한 두 도시 $U$, $V$를 알 수 있다. Subtask 1의 풀이를 데려와보자. 각 도로에 대해 모두 쿼리를 묻는 게 아니라, 도로들에 대해 이분탐색을 해주자. 단, 최단 경로가 여러 가지인 경우를 유의하자. 최단 경로가 여러 가지인 경우 때문에 간선들을 혼잡하게 만들 때 $l$부터 $mid$번 간선까지 혼잡하게 만드는 것이 아니라 $0$번부터 $mid$번 간선까지 혼잡하게 만들어야 한다.

 

$U$, $V$ 중 $S$는 $U$와 가깝고, $T$는 $V$와 더 가깝다. 그러면 모든 도시들을 $U$와 가까운 도시, $V$와 가까운 도시로 분류해줄 수 있다. $U$와 가까운 도시들의 그래프와 $V$와 가까운 도시들의 그래프는 연결그래프이기 때문에 여기서 다시 $U$에 대한 RBO로 이분탐색을 돌려 $S$를 찾고, $V$에 대한 RBO로 이분탐색을 돌려 $T$를 찾는다.

 

맨 처음에 1개의 쿼리, 간선을 찾을 때는 17개의 쿼리가 필요하다.

 

이때 $U$와 가까운 도시의 개수를 $x$라고 하면 $V$와 가까운 도시는 $N-x$개이다. 쿼리의 개수를 구해보자.

$\lceil\log_{2}(x) \rceil + \lceil\log_{2}(N-x)\rceil \leq \lfloor\log_{2}(x(N-x))\rfloor+2 \leq \lfloor \log_{2}(\frac{N^2}{4}) \rfloor + 2 \leq \lfloor 2\log_{2}(N) \rfloor = \lfloor 32.915... \rfloor = 32$

Q. 더 간단하게 할 수는 없나요? 

A. 제 능지의 한계입니다. 부등식 남발하다 32 넘을 뻔했네요.

 

따라서 필요한 쿼리의 최대 개수는 1 + 17 + 32 = 50이고, 만점을 받을 수 있다.

 

<소스 코드>

#include "highway.h"
#include <bits/stdc++.h>


using namespace std;
typedef long long ll;

vector<pair<int, int>> adj[90002];
vector<int> w;
int M;
bool visited[90002];
int dist[90002][2];
vector<int> v[2];
int K = -1, S = -1, T = -1;

void bfs(int x, int N, int t)
{
    for(int i=0;i<N;i++) visited[i] = false;
    visited[x] = true;
    queue<int> q;
    q.push(x);
    while(!q.empty())
    {
        int curr = q.front();
        q.pop();

        for(auto u : adj[curr])
        {
            int i = u.first, j = u.second;
            if(!visited[i])
            {
                visited[i] = true;
                q.push(i);
                dist[i][t] = dist[curr][t] + 1;
            }
        }
    }
}

void makezero()
{
    for(int i=0;i<M;i++) w[i] = 0;
}

bool cmp(int x, int y)
{
    return dist[x][0] > dist[y][0];
}

bool cmp2(int x, int y)
{
    return dist[x][1] > dist[y][1];
}

void binarysearch(int l, int r, ll zerotoll, int k)
{
    if(l == r)
    {
        if(k == 0) S = v[k][l];
        if(k == 1) T = v[k][l];
        return;
    }
    int mid = (l + r)/2;

    makezero();
    for(int i=l;i<=mid;i++)
    {
        for(auto u : adj[v[k][i]])
        {
            w[u.second] = 1;
        }
    }
    ll toll = ask(w);

    if(toll > zerotoll) binarysearch(l, mid, zerotoll, k);
    else binarysearch(mid+1, r, zerotoll, k);
}

void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) {
    M = U.size();
    for(int j=0;j<M;j++) { adj[U[j]].push_back({V[j], j}); adj[V[j]].push_back({U[j], j}); }
    w.resize(M);
    makezero();
    ll zerotoll = ask(w);

    int l = 0, r = M-1;
    while(l < r)
    {
        makezero();
        int mid = (l + r)/2;
        for(int i=0;i<=mid;i++)
        {
            w[i] = 1;
        }
        if(ask(w) > zerotoll) r = mid;
        else l = mid+1;
    }
    bfs(U[l], N, 0);
    bfs(V[l], N, 1);
    for(int i=0;i<N;i++)
    {
        if(dist[i][0] < dist[i][1]) v[0].push_back(i);
        else v[1].push_back(i);
    }
    sort(v[0].begin(), v[0].end(), cmp);
    sort(v[1].begin(), v[1].end(), cmp2);

    binarysearch(0, (int)v[0].size()-1, zerotoll, 0);
    binarysearch(0, (int)v[1].size()-1, zerotoll, 1);

    answer(S, T);
}