oj.uz

Submission #301787

# Submission time Handle Problem Language Result Execution time Memory
301787 2020-09-18T08:08:14 Z tatyam Saveit (IOI10_saveit) C++17
100 / 100
 689 ms 11504 KB 
#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);
    }
}
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 11504 KB Output is correct - 67050 call(s) of encode_bit()
2 Correct 4 ms 4816 KB Output is correct - 4795 call(s) of encode_bit()
3 Correct 396 ms 5588 KB Output is correct - 66050 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 7965 call(s) of encode_bit()
5 Correct 391 ms 5760 KB Output is correct - 66050 call(s) of encode_bit()
6 Correct 449 ms 5876 KB Output is correct - 67050 call(s) of encode_bit()
7 Correct 470 ms 6288 KB Output is correct - 67050 call(s) of encode_bit()
8 Correct 419 ms 5816 KB Output is correct - 66660 call(s) of encode_bit()
9 Correct 445 ms 5812 KB Output is correct - 67050 call(s) of encode_bit()
10 Correct 454 ms 5616 KB Output is correct - 67050 call(s) of encode_bit()
11 Correct 443 ms 5676 KB Output is correct - 67050 call(s) of encode_bit()
12 Correct 445 ms 5832 KB Output is correct - 67050 call(s) of encode_bit()
13 Correct 473 ms 6548 KB Output is correct - 67050 call(s) of encode_bit()
14 Correct 441 ms 5788 KB Output is correct - 67050 call(s) of encode_bit()
15 Correct 441 ms 5868 KB Output is correct - 67050 call(s) of encode_bit()
16 Correct 466 ms 6244 KB Output is correct - 67050 call(s) of encode_bit()
17 Correct 463 ms 6128 KB Output is correct - 67050 call(s) of encode_bit()
18 Correct 471 ms 6264 KB Output is correct - 67050 call(s) of encode_bit()
19 Correct 453 ms 6220 KB Output is correct - 67050 call(s) of encode_bit()
20 Correct 485 ms 6820 KB Output is correct - 67050 call(s) of encode_bit()
21 Correct 490 ms 6816 KB Output is correct - 67050 call(s) of encode_bit()
22 Correct 471 ms 6576 KB Output is correct - 67050 call(s) of encode_bit()
23 Correct 504 ms 7456 KB Output is correct - 67050 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 11504 KB Output is correct - 67050 call(s) of encode_bit()
2 Correct 4 ms 4816 KB Output is correct - 4795 call(s) of encode_bit()
3 Correct 396 ms 5588 KB Output is correct - 66050 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 7965 call(s) of encode_bit()
5 Correct 391 ms 5760 KB Output is correct - 66050 call(s) of encode_bit()
6 Correct 449 ms 5876 KB Output is correct - 67050 call(s) of encode_bit()
7 Correct 470 ms 6288 KB Output is correct - 67050 call(s) of encode_bit()
8 Correct 419 ms 5816 KB Output is correct - 66660 call(s) of encode_bit()
9 Correct 445 ms 5812 KB Output is correct - 67050 call(s) of encode_bit()
10 Correct 454 ms 5616 KB Output is correct - 67050 call(s) of encode_bit()
11 Correct 443 ms 5676 KB Output is correct - 67050 call(s) of encode_bit()
12 Correct 445 ms 5832 KB Output is correct - 67050 call(s) of encode_bit()
13 Correct 473 ms 6548 KB Output is correct - 67050 call(s) of encode_bit()
14 Correct 441 ms 5788 KB Output is correct - 67050 call(s) of encode_bit()
15 Correct 441 ms 5868 KB Output is correct - 67050 call(s) of encode_bit()
16 Correct 466 ms 6244 KB Output is correct - 67050 call(s) of encode_bit()
17 Correct 463 ms 6128 KB Output is correct - 67050 call(s) of encode_bit()
18 Correct 471 ms 6264 KB Output is correct - 67050 call(s) of encode_bit()
19 Correct 453 ms 6220 KB Output is correct - 67050 call(s) of encode_bit()
20 Correct 485 ms 6820 KB Output is correct - 67050 call(s) of encode_bit()
21 Correct 490 ms 6816 KB Output is correct - 67050 call(s) of encode_bit()
22 Correct 471 ms 6576 KB Output is correct - 67050 call(s) of encode_bit()
23 Correct 504 ms 7456 KB Output is correct - 67050 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 11504 KB Output is correct - 67050 call(s) of encode_bit()
2 Correct 4 ms 4816 KB Output is correct - 4795 call(s) of encode_bit()
3 Correct 396 ms 5588 KB Output is correct - 66050 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 7965 call(s) of encode_bit()
5 Correct 391 ms 5760 KB Output is correct - 66050 call(s) of encode_bit()
6 Correct 449 ms 5876 KB Output is correct - 67050 call(s) of encode_bit()
7 Correct 470 ms 6288 KB Output is correct - 67050 call(s) of encode_bit()
8 Correct 419 ms 5816 KB Output is correct - 66660 call(s) of encode_bit()
9 Correct 445 ms 5812 KB Output is correct - 67050 call(s) of encode_bit()
10 Correct 454 ms 5616 KB Output is correct - 67050 call(s) of encode_bit()
11 Correct 443 ms 5676 KB Output is correct - 67050 call(s) of encode_bit()
12 Correct 445 ms 5832 KB Output is correct - 67050 call(s) of encode_bit()
13 Correct 473 ms 6548 KB Output is correct - 67050 call(s) of encode_bit()
14 Correct 441 ms 5788 KB Output is correct - 67050 call(s) of encode_bit()
15 Correct 441 ms 5868 KB Output is correct - 67050 call(s) of encode_bit()
16 Correct 466 ms 6244 KB Output is correct - 67050 call(s) of encode_bit()
17 Correct 463 ms 6128 KB Output is correct - 67050 call(s) of encode_bit()
18 Correct 471 ms 6264 KB Output is correct - 67050 call(s) of encode_bit()
19 Correct 453 ms 6220 KB Output is correct - 67050 call(s) of encode_bit()
20 Correct 485 ms 6820 KB Output is correct - 67050 call(s) of encode_bit()
21 Correct 490 ms 6816 KB Output is correct - 67050 call(s) of encode_bit()
22 Correct 471 ms 6576 KB Output is correct - 67050 call(s) of encode_bit()
23 Correct 504 ms 7456 KB Output is correct - 67050 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 689 ms 11504 KB Output is correct - 67050 call(s) of encode_bit()
2 Correct 4 ms 4816 KB Output is correct - 4795 call(s) of encode_bit()
3 Correct 396 ms 5588 KB Output is correct - 66050 call(s) of encode_bit()
4 Correct 4 ms 4736 KB Output is correct - 7965 call(s) of encode_bit()
5 Correct 391 ms 5760 KB Output is correct - 66050 call(s) of encode_bit()
6 Correct 449 ms 5876 KB Output is correct - 67050 call(s) of encode_bit()
7 Correct 470 ms 6288 KB Output is correct - 67050 call(s) of encode_bit()
8 Correct 419 ms 5816 KB Output is correct - 66660 call(s) of encode_bit()
9 Correct 445 ms 5812 KB Output is correct - 67050 call(s) of encode_bit()
10 Correct 454 ms 5616 KB Output is correct - 67050 call(s) of encode_bit()
11 Correct 443 ms 5676 KB Output is correct - 67050 call(s) of encode_bit()
12 Correct 445 ms 5832 KB Output is correct - 67050 call(s) of encode_bit()
13 Correct 473 ms 6548 KB Output is correct - 67050 call(s) of encode_bit()
14 Correct 441 ms 5788 KB Output is correct - 67050 call(s) of encode_bit()
15 Correct 441 ms 5868 KB Output is correct - 67050 call(s) of encode_bit()
16 Correct 466 ms 6244 KB Output is correct - 67050 call(s) of encode_bit()
17 Correct 463 ms 6128 KB Output is correct - 67050 call(s) of encode_bit()
18 Correct 471 ms 6264 KB Output is correct - 67050 call(s) of encode_bit()
19 Correct 453 ms 6220 KB Output is correct - 67050 call(s) of encode_bit()
20 Correct 485 ms 6820 KB Output is correct - 67050 call(s) of encode_bit()
21 Correct 490 ms 6816 KB Output is correct - 67050 call(s) of encode_bit()
22 Correct 471 ms 6576 KB Output is correct - 67050 call(s) of encode_bit()
23 Correct 504 ms 7456 KB Output is correct - 67050 call(s) of encode_bit()