Submission #301787

#	Time	Username	Problem	Language	Result	Execution time	Memory
301787		tatyam	Saveit (IOI10_saveit)	C++17	100 / 100	689 ms	11504 KiB

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(int N, int H, int P, int A[], 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);
void decode(int N, int H);


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]);
    }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode_BigInt(std::vector<int>)':
encoder.cpp:22:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 1585>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |         for(int i = 0; i < a.size() - 1; i++){
      |                        ~~^~~~~~~~~~~~~~

decoder.cpp: In function 'std::vector<int> decode_BigInt(int)':
decoder.cpp:25:51: warning: comparison of integer expressions of different signedness: 'int' and 'std::array<int, 1585>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for(int i = a.size() - 1; i--; ) if(i + 2 < a.size() && a[i + 2] || a[i + 1] && a[i]){
      |                                             ~~~~~~^~~~~~~~~~
decoder.cpp:25:62: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   25 |         for(int i = a.size() - 1; i--; ) if(i + 2 < a.size() && a[i + 2] || a[i + 1] && a[i]){

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25