Submission #747197

#	Time	Username	Problem	Language	Result	Execution time	Memory
747197		finn__	Saveit (IOI10_saveit)	C++17	0 / 100	216 ms	10364 KiB

encoder

#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>
using namespace std;

void encode_package(int p[3])
{
    int z = 0;
    for (size_t i = 0; i < 3; ++i)
        z = z * 3 + p[i] + 1;
    for (size_t i = 0; i < 5; ++i)
        encode_bit((z >> (4 - i)) & 1);
}

void encode(int n, int h, int m, int *a, int *b)
{
    vector<vector<int>> g(n), d(h, vector<int>(n, -1));
    vector<int> p(n);
    for (size_t i = 0; i < m; ++i)
        g[a[i]].push_back(b[i]), g[b[i]].push_back(a[i]);

    for (size_t i = 0; i < h; ++i)
    {
        queue<int> q;
        q.push(i);
        d[i][i] = 0;
        while (!q.empty())
        {
            int u = q.front();
            q.pop();
            for (int const &v : g[u])
                if (d[i][v] == -1)
                {
                    d[i][v] = d[i][u] + 1;
                    q.push(v);
                    if (!i)
                        p[v] = u;
                }
        }
    }

    for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
        for (size_t j = 0; j < 10; ++j)
            encode_bit((p[i] >> j) & 1);

    int c[3];
    size_t l = 0;
    for (size_t i = 1; i < n; ++i) /* encode distance changes */
        for (size_t k = 0; k < h; ++k)
        {
            c[l++] = d[k][i] - d[k][p[i]];
            if (l == 3)
                encode_package(c), l = 0;
        }
    if (l)
        encode_package(c);
}

decoder

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>
using namespace std;

void decode_package(int p[3])
{
    int z = 0;
    for (size_t i = 0; i < 5; ++i)
        z = (z << 1) | decode_bit();
    for (size_t i = 0; i < 3; ++i)
        p[2 - i] = (z % 3) - 1, z /= 3;
}

void decode(int n, int h)
{
    vector<vector<int>> d(h, vector<int>(n));
    vector<int> p(n);
    hops(0, 0, 0);
    for (size_t i = 1; i < n; ++i)
    {
        for (size_t j = 0; j < 10; ++j)
            p[i] = (p[i] << 1) | decode_bit();
        d[0][i] = d[0][p[i]] + 1;
        hops(0, i, d[0][i]);
    }

    size_t l = 0;
    int c[3];
    for (size_t i = 1; i < n; ++i)
        for (size_t k = 0; k < h; ++k)
        {
            if (l == 3)
                decode_package(c), l = 0;
            d[k][i] = d[k][p[i]] + c[l++];
            hops(k, i, d[k][i]);
        }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:20:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
encoder.cpp:23:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   23 |     for (size_t i = 0; i < h; ++i)
      |                        ~~^~~
encoder.cpp:43:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   43 |     for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
      |                        ~~^~~
encoder.cpp:49:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   49 |     for (size_t i = 1; i < n; ++i) /* encode distance changes */
      |                        ~~^~~
encoder.cpp:50:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   50 |         for (size_t k = 0; k < h; ++k)
      |                            ~~^~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:21:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   21 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
decoder.cpp:31:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   31 |     for (size_t i = 1; i < n; ++i)
      |                        ~~^~~
decoder.cpp:32:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |         for (size_t k = 0; k < h; ++k)
      |                            ~~^~~

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