---
tags: IOI
---
# IOI2010 Day2-4 保存せよ (Saveit)

解きたかった…(๑•̥ૅㅁ•̥๑)

## 問題

https://www.ioi-jp.org/ioi/2010/tasks/tasks_jpn/day2/t4_saveit/index.html
https://oj.uz/problem/view/IOI10_saveit

$N$ 頂点 $P$ 辺の連結な無向グラフが与えられます。
$0$ 以上 $H$ 未満の全ての $h$ について、頂点 $h$ から全ての頂点への最短経路の長さを求めてください。
ただし、 encoder と decoder の 2 つを実装してください。
- encoder : グラフの情報が与えられるので、 decoder に $70000$ bit までの情報を渡す
- decoder : encoder から渡された情報から、最短経路の長さを答える

$N ≤ 10^3$
$H ≤ 36$

## 考察

隣接行列を渡す : $10^6$ bit　(ここまで 25 点)
答えをそのまま渡す : $360000$ bit　(ここまで 50 点)

なにかの性質を使って考えられる値の範囲を狭める必要がある。

使えそうないい感じの性質　な〜んだ？

:::spoiler これ
(頂点 $\large a$ と頂点 $\large b$ が繋がっている) $\large \Longrightarrow |\text{dist}(i,a)-\text{dist}(i,b)|≤1$
:::

<br>

:::spoiler 解説
まず、全域木を 1 つとって decoder に送る。
これは、頂点 $\large 0$ を根として、親が何かを送れば $\large N\log_2N$ bit でできる。
次に、最短経路の長さを送る。

1. $\large h$ から BFS して、最短経路の長さを求める
2. 全域木の全ての辺について、最短経路の長さの差を取る
- (頂点 $\large a$ と頂点 $\large b$ が繋がっている) $\large \Longrightarrow |\text{dist}(i,a)-\text{dist}(i,b)|≤1$ より、差は $\large -1,0,1$ のいずれか
3. 差を送ると、 $\large N\times\log_23≤1585$ bit で送れる
4. $\large h$ から累積和を取ると、最短経路の長さが復元できる

全ての $\large h$ についてこれを行うと、全体で $\large N\log_2N+HN\log_23≤67060$ bit でできる。
:::

## 実装

https://oj.uz/submission/301787

### encoder

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3fffffff;
template<class T> bool chmin(T& a, const T& b){ if(a > b){ a = b; return 1; } return 0; }
 
void encode_bit(int b);
 
 
void encode_num(int num, int size){
    for(int i = size; i--; ) encode_bit(num >> i & 1);
}
using BigInt = array<int, 1585>; // 1000 * log_2(3) = 1585
void encode_BigInt(vector<int> B){ // ternary to binary
    BigInt a;
    a.fill(0);
    reverse(B.begin(), B.end());
    for(int b : B){
        for(int i = a.size() - 1; i--; ) a[i + 1] += a[i];
        if(b & 1) a[0]++;
        if(b & 2) a[1]++;
        for(int i = 0; i < a.size() - 1; i++){
            a[i + 1] += a[i] >> 1;
            a[i] &= 1;
        }
    }
    for(int i : a) encode_bit(i);
}
void encode(int N, int H, int P, int A[], int B[]){
    vector<vector<int>> g(N);
    for(int i = 0; i < P; i++){
        g[A[i]].push_back(B[i]);
        g[B[i]].push_back(A[i]);
    }
    vector parent(N, -1);
    auto dfs = [&](int from, int at, auto dfs) -> void {
        for(int i : g[at]) if(parent[i] == -1){
            parent[i] = at;
            dfs(at, i, dfs);
        }
    };
    dfs(-1, 0, dfs);
    vector<pair<int, int>> edge;
    for(int i = 1; i < N; i++){
        encode_num(parent[i], 10);
        edge.emplace_back(parent[i], i);
    }
    for(int root = 0; root < H; root++){
        vector<int> cost(N, INF);
        vector<int> q;
        cost[root] = 0;
        q.push_back(root);
        q.reserve(N);
        for(auto p = q.begin(); p != q.end(); p++){
            const int at = *p;
            for(int i : g[at]) if(chmin(cost[i], cost[at] + 1)) q.push_back(i);
        }
        vector<int> diff(N - 1);
        for(int i = 0; i < N - 1; i++){
            const auto [a, b] = edge[i];
            diff[i] = cost[b] - cost[a] + 1;
        }
        encode_BigInt(diff);
    }
}

### decoder

#include <bits/stdc++.h>
using namespace std;
 
int decode_bit();
void hops(int h, int c, int d);
 
 
using BigInt = array<int, 1585>; // 1000 * log_2(3) = 1585
int decode_num(int size){
    int ans = 0;
    while(size--){
        ans <<= 1;
        ans |= decode_bit();
    }
    return ans;
}
vector<int> decode_BigInt(int size){ // binary to ternary
    BigInt a;
    for(int& i : a) i = decode_bit();
    vector<int> ans(size);
    for(int& res : ans){
        BigInt b;
        b.fill(0);
        for(int i = a.size() - 1; i--; ) if(i + 2 < a.size() && a[i + 2] || a[i + 1] && a[i]){
            b[i] = 1;
            if(a[i + 1] && a[i]){
                a[i + 1] = 0;
                a[i] = 0;
            }
            else{
                if(a[i]){
                    a[i] = 0;
                    a[i + 1] = 1;
                }
                else a[i] = 1;
            }
        }
        if(a[0]) res |= 1;
        if(a[1]) res |= 2;
        swap(a, b);
    }
    return ans;
}
 
void decode(int N, int H){
    vector<pair<int, int>> edge(N - 1);
    for(int i = 1; i < N; i++) edge[i - 1] = {decode_num(10), i};
    for(int root = 0; root < H; root++){
        auto diff = decode_BigInt(N - 1);
        for(int& i : diff) i--;
        vector<vector<pair<int, int>>> g(N);
        for(int i = 0; i < N - 1; i++){
            const auto [a, b] = edge[i];
            const int c = diff[i];
            g[a].emplace_back(b, c);
            g[b].emplace_back(a, -c);
        }
        vector cost(N, -1);
        cost[root] = 0;
        auto dfs = [&](int from, int at, auto dfs) -> void {
            for(auto [i, c] : g[at]) if(cost[i] == -1){
                cost[i] = cost[at] + c;
                dfs(at, i, dfs);
            }
        };
        dfs(-1, root, dfs);
        for(int i = 0; i < N; i++) hops(root, i, cost[i]);
    }
}