Submission #747197

# Submission time Handle Problem Language Result Execution time Memory
747197 2023-05-23T22:10:52 Z finn__ Saveit (IOI10_saveit) C++17
0 / 100
216 ms 10364 KB
#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);
}
#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

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)
      |                            ~~^~~
# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10364 KB duplicate hops call
2 Incorrect 3 ms 4604 KB duplicate hops call
3 Incorrect 28 ms 5396 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 28 ms 5760 KB duplicate hops call
6 Incorrect 24 ms 5736 KB duplicate hops call
7 Incorrect 39 ms 6036 KB duplicate hops call
8 Incorrect 20 ms 5404 KB wrong parameter
9 Incorrect 23 ms 5628 KB wrong parameter
10 Incorrect 21 ms 5652 KB wrong parameter
11 Incorrect 28 ms 5712 KB wrong parameter
12 Incorrect 22 ms 5408 KB wrong parameter
13 Incorrect 52 ms 6200 KB duplicate hops call
14 Incorrect 20 ms 5592 KB wrong parameter
15 Incorrect 27 ms 5572 KB wrong parameter
16 Incorrect 41 ms 5928 KB wrong parameter
17 Incorrect 38 ms 5948 KB wrong parameter
18 Incorrect 46 ms 6284 KB duplicate hops call
19 Incorrect 28 ms 5892 KB wrong parameter
20 Incorrect 60 ms 6556 KB duplicate hops call
21 Incorrect 52 ms 6668 KB duplicate hops call
22 Incorrect 43 ms 6180 KB duplicate hops call
23 Incorrect 95 ms 6948 KB duplicate hops call
# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10364 KB duplicate hops call
2 Incorrect 3 ms 4604 KB duplicate hops call
3 Incorrect 28 ms 5396 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 28 ms 5760 KB duplicate hops call
6 Incorrect 24 ms 5736 KB duplicate hops call
7 Incorrect 39 ms 6036 KB duplicate hops call
8 Incorrect 20 ms 5404 KB wrong parameter
9 Incorrect 23 ms 5628 KB wrong parameter
10 Incorrect 21 ms 5652 KB wrong parameter
11 Incorrect 28 ms 5712 KB wrong parameter
12 Incorrect 22 ms 5408 KB wrong parameter
13 Incorrect 52 ms 6200 KB duplicate hops call
14 Incorrect 20 ms 5592 KB wrong parameter
15 Incorrect 27 ms 5572 KB wrong parameter
16 Incorrect 41 ms 5928 KB wrong parameter
17 Incorrect 38 ms 5948 KB wrong parameter
18 Incorrect 46 ms 6284 KB duplicate hops call
19 Incorrect 28 ms 5892 KB wrong parameter
20 Incorrect 60 ms 6556 KB duplicate hops call
21 Incorrect 52 ms 6668 KB duplicate hops call
22 Incorrect 43 ms 6180 KB duplicate hops call
23 Incorrect 95 ms 6948 KB duplicate hops call
# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10364 KB duplicate hops call
2 Incorrect 3 ms 4604 KB duplicate hops call
3 Incorrect 28 ms 5396 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 28 ms 5760 KB duplicate hops call
6 Incorrect 24 ms 5736 KB duplicate hops call
7 Incorrect 39 ms 6036 KB duplicate hops call
8 Incorrect 20 ms 5404 KB wrong parameter
9 Incorrect 23 ms 5628 KB wrong parameter
10 Incorrect 21 ms 5652 KB wrong parameter
11 Incorrect 28 ms 5712 KB wrong parameter
12 Incorrect 22 ms 5408 KB wrong parameter
13 Incorrect 52 ms 6200 KB duplicate hops call
14 Incorrect 20 ms 5592 KB wrong parameter
15 Incorrect 27 ms 5572 KB wrong parameter
16 Incorrect 41 ms 5928 KB wrong parameter
17 Incorrect 38 ms 5948 KB wrong parameter
18 Incorrect 46 ms 6284 KB duplicate hops call
19 Incorrect 28 ms 5892 KB wrong parameter
20 Incorrect 60 ms 6556 KB duplicate hops call
21 Incorrect 52 ms 6668 KB duplicate hops call
22 Incorrect 43 ms 6180 KB duplicate hops call
23 Incorrect 95 ms 6948 KB duplicate hops call
# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10364 KB duplicate hops call
2 Incorrect 3 ms 4604 KB duplicate hops call
3 Incorrect 28 ms 5396 KB wrong parameter
4 Incorrect 2 ms 4604 KB duplicate hops call
5 Incorrect 28 ms 5760 KB duplicate hops call
6 Incorrect 24 ms 5736 KB duplicate hops call
7 Incorrect 39 ms 6036 KB duplicate hops call
8 Incorrect 20 ms 5404 KB wrong parameter
9 Incorrect 23 ms 5628 KB wrong parameter
10 Incorrect 21 ms 5652 KB wrong parameter
11 Incorrect 28 ms 5712 KB wrong parameter
12 Incorrect 22 ms 5408 KB wrong parameter
13 Incorrect 52 ms 6200 KB duplicate hops call
14 Incorrect 20 ms 5592 KB wrong parameter
15 Incorrect 27 ms 5572 KB wrong parameter
16 Incorrect 41 ms 5928 KB wrong parameter
17 Incorrect 38 ms 5948 KB wrong parameter
18 Incorrect 46 ms 6284 KB duplicate hops call
19 Incorrect 28 ms 5892 KB wrong parameter
20 Incorrect 60 ms 6556 KB duplicate hops call
21 Incorrect 52 ms 6668 KB duplicate hops call
22 Incorrect 43 ms 6180 KB duplicate hops call
23 Incorrect 95 ms 6948 KB duplicate hops call