oj.uz

Submission #747199

# Submission time Handle Problem Language Result Execution time Memory
747199 2023-05-23T22:17:58 Z finn__ Saveit (IOI10_saveit) C++17
0 / 100
 203 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 = 4; i < 5; --i)
        encode_bit((z >> i) & 1);
}

void encode(int n, int h, int m, int *a, int *b)
{
    if (!h)
        return;
    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 = 9; 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 = 1; 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)
{
    if (!h)
        return;
    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 = 1; 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:22:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   22 |     for (size_t i = 0; i < m; ++i)
      |                        ~~^~~
encoder.cpp:25:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   25 |     for (size_t i = 0; i < h; ++i)
      |                        ~~^~~
encoder.cpp:45:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   45 |     for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
      |                        ~~^~~
encoder.cpp:51:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   51 |     for (size_t i = 1; i < n; ++i) /* encode distance changes */
      |                        ~~^~~
encoder.cpp:52:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   52 |         for (size_t k = 1; k < h; ++k)
      |                            ~~^~~

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 10364 KB wrong parameter
2 Incorrect 2 ms 4616 KB wrong parameter
3 Incorrect 20 ms 5436 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5636 KB wrong parameter
6 Incorrect 19 ms 5740 KB wrong parameter
7 Incorrect 34 ms 6172 KB wrong parameter
8 Incorrect 17 ms 5512 KB wrong parameter
9 Incorrect 18 ms 5628 KB wrong parameter
10 Incorrect 17 ms 5632 KB wrong parameter
11 Incorrect 23 ms 5744 KB wrong parameter
12 Incorrect 19 ms 5488 KB wrong parameter
13 Incorrect 46 ms 6208 KB wrong parameter
14 Incorrect 20 ms 5608 KB wrong parameter
15 Incorrect 18 ms 5672 KB wrong parameter
16 Incorrect 32 ms 5920 KB wrong parameter
17 Incorrect 41 ms 6064 KB wrong parameter
18 Incorrect 56 ms 6284 KB wrong parameter
19 Incorrect 32 ms 5772 KB wrong parameter
20 Incorrect 57 ms 6608 KB wrong parameter
21 Incorrect 61 ms 6632 KB wrong parameter
22 Incorrect 40 ms 6204 KB wrong parameter
23 Incorrect 63 ms 6844 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 10364 KB wrong parameter
2 Incorrect 2 ms 4616 KB wrong parameter
3 Incorrect 20 ms 5436 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5636 KB wrong parameter
6 Incorrect 19 ms 5740 KB wrong parameter
7 Incorrect 34 ms 6172 KB wrong parameter
8 Incorrect 17 ms 5512 KB wrong parameter
9 Incorrect 18 ms 5628 KB wrong parameter
10 Incorrect 17 ms 5632 KB wrong parameter
11 Incorrect 23 ms 5744 KB wrong parameter
12 Incorrect 19 ms 5488 KB wrong parameter
13 Incorrect 46 ms 6208 KB wrong parameter
14 Incorrect 20 ms 5608 KB wrong parameter
15 Incorrect 18 ms 5672 KB wrong parameter
16 Incorrect 32 ms 5920 KB wrong parameter
17 Incorrect 41 ms 6064 KB wrong parameter
18 Incorrect 56 ms 6284 KB wrong parameter
19 Incorrect 32 ms 5772 KB wrong parameter
20 Incorrect 57 ms 6608 KB wrong parameter
21 Incorrect 61 ms 6632 KB wrong parameter
22 Incorrect 40 ms 6204 KB wrong parameter
23 Incorrect 63 ms 6844 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 10364 KB wrong parameter
2 Incorrect 2 ms 4616 KB wrong parameter
3 Incorrect 20 ms 5436 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5636 KB wrong parameter
6 Incorrect 19 ms 5740 KB wrong parameter
7 Incorrect 34 ms 6172 KB wrong parameter
8 Incorrect 17 ms 5512 KB wrong parameter
9 Incorrect 18 ms 5628 KB wrong parameter
10 Incorrect 17 ms 5632 KB wrong parameter
11 Incorrect 23 ms 5744 KB wrong parameter
12 Incorrect 19 ms 5488 KB wrong parameter
13 Incorrect 46 ms 6208 KB wrong parameter
14 Incorrect 20 ms 5608 KB wrong parameter
15 Incorrect 18 ms 5672 KB wrong parameter
16 Incorrect 32 ms 5920 KB wrong parameter
17 Incorrect 41 ms 6064 KB wrong parameter
18 Incorrect 56 ms 6284 KB wrong parameter
19 Incorrect 32 ms 5772 KB wrong parameter
20 Incorrect 57 ms 6608 KB wrong parameter
21 Incorrect 61 ms 6632 KB wrong parameter
22 Incorrect 40 ms 6204 KB wrong parameter
23 Incorrect 63 ms 6844 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 10364 KB wrong parameter
2 Incorrect 2 ms 4616 KB wrong parameter
3 Incorrect 20 ms 5436 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 18 ms 5636 KB wrong parameter
6 Incorrect 19 ms 5740 KB wrong parameter
7 Incorrect 34 ms 6172 KB wrong parameter
8 Incorrect 17 ms 5512 KB wrong parameter
9 Incorrect 18 ms 5628 KB wrong parameter
10 Incorrect 17 ms 5632 KB wrong parameter
11 Incorrect 23 ms 5744 KB wrong parameter
12 Incorrect 19 ms 5488 KB wrong parameter
13 Incorrect 46 ms 6208 KB wrong parameter
14 Incorrect 20 ms 5608 KB wrong parameter
15 Incorrect 18 ms 5672 KB wrong parameter
16 Incorrect 32 ms 5920 KB wrong parameter
17 Incorrect 41 ms 6064 KB wrong parameter
18 Incorrect 56 ms 6284 KB wrong parameter
19 Incorrect 32 ms 5772 KB wrong parameter
20 Incorrect 57 ms 6608 KB wrong parameter
21 Incorrect 61 ms 6632 KB wrong parameter
22 Incorrect 40 ms 6204 KB wrong parameter
23 Incorrect 63 ms 6844 KB wrong parameter