IOI 2020 day2 - stations

문제 링크 : www.acmicpc.net/problem/19938

문제 소개

두 가지 행동을 해야하는 투스텝 문제이다.
1. 트리에 적당히 라벨링한다.
2. 시작 라벨, 끝 라벨만 보고, 가야하는 바로 다음 라벨을 구한다.

이때 1->2 로 전달되는 정보는 시작,끝,주위 라벨 뿐이다.

문제 풀이(+의식의 흐름)

part 1. 문제를 읽으면서 생각한 것들 - 1차 생각, 해야할 일들 정리

X

문제 자체를 이해하는데 꽤나 오랜 시간이 걸렸다. 결과적인 부분은 위의 내용밖에 없는데, 전체적인 프로그램의 작동방식의 흐름을 이해하지 못해서 힘들었다.
1과 2 사이의 정보를 프로그램을 꺼서 데이터를 날리고 다시 켜서 실행시키는 방식인 것을 제대로 알지 못했다.

part 2. 출발지와 목적지.

결국 중요한 것은 1->2 에서 라벨링만 해서 보낼 수 있고, 라벨링을 통해서 정보를 전달하는 것이다. 즉, 어떠한 정보들을 라벨에 담아 전달할 지를 선택해야 한다.

트리에서 생각을 해보자. 출발지인 점 A를 기준으로 위로 가야할 수도 있고, 아래로 가야할 수도 있다. 일단은 목적지가 아래쪽에 있다고 생각해보자. 즉, B가 A의 서브트리에 속해있다고 가정해보자. A의 자식 노드들이 여러개 있을 것이다. x1,x2,x3... B는 이 중 한 서브트리에 속해있다. 생각을 해보면, A에서 B로 향하는 다음 노드는 B가 속해있는 서브트리의 루트라는 것을 알 수 있다. 따라서 우리는 x1이 루트인 서브트리에 속해있는지, x2가 루트인 서브트리에 속해있는지.... 를 구분하면 된다.

part 3. 구분과 전달 정보

 이때 당연히 모든 노드에 대해서 같은 정보를 전달할 것이라고 생각했다. 즉, x1~xi의 정보 y와 B의 정보 y를 가지고 B가 어느 노드의 서브트리에 속해있는지를 알 수 있게 하는 y를 찾는 것이 목표이다.

여기서 dfs ordering이 생각났다. dfs ordering에서 in과 out에 대한 정보를 가지고 있다면 조상 노드인 p와 손자 노드인 s에 대해서 in[p]<in[s]<=out[s]<=out[p]가 성립하기 때문이다. 전체 수 구간이 자식 노드들의 in,out으로 인해 겹치는 구간 없이 쪼개지기 때문에 목적지의 in,out 값을 가지고 어느 자식 노드의 서브트리에 속해있는지 구분할 수 있다. 
따라서 in,out 값을 동시에 라벨링하면 된다.

in 값에도 1000개가 있고, out 값에도 1000개가 있기 때문에 1000000가지가 가능하고, 따라서 k가 1000000이상인 경우에만 문제를 해결할 수 있다.

part 4. 라벨링 범위를 1000으로 줄이기

가장 먼저 생각한 아이디어는 in 값을 라벨링해서 전달하는 방법이었다. out 값은 서로 같을 수도 있지만, in값은 1~1000으로 모두 다르기 때문에 가능할지에 대해서 생각을 해봤다. 가능 할 것 처럼 보였다. 자식 x1,x2,x3..,xi 가 있을 때 목적지 f가 $in[x_j]\leq in[f]< in[x_j+1]$  이면 $x_j$의 자식인것으로 구분할 수 있다.

그래서 문제를 해결할 수 있을 것 처럼 보였지만, 한가지 문제가 생겼다. 목적지가 출발지의 서브트리에 속해있지 않을 수도 있다는 것이다. $in[x_i]\leq in[f]$ 인 경우에는 xi의 서브트리에 목적지가 있는지 그 밖에 xi가 있는지 알 수가 없다는 것이 문제이다. 이에 대해서 정말 오래 고민해봤지만, dfs ordering을 어떤식으로 해도 이 둘을 구분할 방법이 존재 하지 않았다. 그래서 직접 그려서 관찰을 해봤다.

part 5. dfs ordering과 구역 분리에 관한 고찰

출발지 p의 자식노드가 3개 있다고 하자. 이들을 x1,x2,x3라고 하자. 이러면 우리의 목표는 전체 수 구간을 5개로 쪼개는 것이다. ~in[p], in[x1]~out[x1], in[x2]~out[x2], in[x3]~out[x3], out[p]~의 5가지로 구분해야 하고, 필요한 정보와 쓸 수 있는 정보는 4개이다. 따라서 이론상 4개의 기준으로 5개의 구간을 나누는 것은 가능하다. 하지만, 현재로써의 문제는 in[p]+1=in[x1] 이기 때문에 1개의 정보 손실이 나게 되어 완벽하게 구간을 나누지 못하였다.
여기서 막혀서 계속 고민하다가 되돌아가서 in과 out에 관한 식을 정리해보았다.

in[p]+1=in[x1]
out[x1]+1=in[x2]
out[x2]+1=in[x3]
out[x3]=out[p]

??????? 딱 쓰고 나니까 바로 보였다. 왼쪽에 p,x1,x2,x3 오른쪽에 p,x1,x2,x3 그리고 in out도 정확하게 갈라져 있다. p와 x1,x2,x3의 차이는 깊이의 차이기 때문에 즉, 홀짝으로 나눠서 in과 out을 라벨링하면 된다는 것이다. 

코딩을 하기 위해서는 약간의 관찰이 더 필요할 것이다.

코드

#include "stations.h"
#include <bits/stdc++.h>
using namespace std;
typedef int ll;
#define pb push_back

vector<ll> v[1010101];
ll lab[1010101];
ll vis[1010101];

ll cnt=-1;
void dfs(ll x,ll d){
    vis[x]=1;
    if(d%2){
        cnt++;
        lab[x]=cnt;
    }

    for(auto k:v[x]){
        if(vis[k]) continue;
        vis[k]=1;
        dfs(k,d+1);
    }

    if(d%2==0){
        cnt++;
        lab[x]=cnt;
    }
}

std::vector<int> label(int n, int k, std::vector<int> u, std::vector<int> v2) {
    std::vector<int> labels(n);
    ll i,j,l,m;
     cnt=-1;
    for(i=0;i<n;i++){
        vis[i]=0;
        v[i].clear();
    }
    for(i=0;i<u.size();i++){
        v[u[i]].pb(v2[i]);
        v[v2[i]].pb(u[i]);
    }

    dfs(0,1);

    for (int i = 0; i < n; i++) 
        labels[i] = lab[i];
    
    return labels;
}

int find_next_station(int s, int t, std::vector<int> c) {
    sort(c.begin(), c.end());
    ll i,j,k,l,m,n;
    if(c[0]<s){
        if(t<=c[0]||s<=t)
            return c[0];
        
        c.pb(s);
        for(i=0;i<c.size();i++)
            if(c[i]<=t&&t<c[i+1])
                return c[i];
            
    
    }
    else{
        ll sz=c.size();
        if(t>=c[sz-1]||s>=t)
            return c[sz-1];
        
        c.pb(s);
        sort(c.begin(), c.end());
        for(i=0;i<c.size();i++)
            if(c[i]<t&&t<=c[i+1])
                return c[i+1];
        
    }
}