oj.uz

Submission #747202

# Submission time Handle Problem Language Result Execution time Memory
747202 2023-05-23T22:37:53 Z finn__ Saveit (IOI10_saveit) C++17
0 / 100
 274 ms 10436 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), bfs_order;
    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 < n; ++i)
        sort(g[i].begin(), g[i].end());

    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, bfs_order.push_back(v);
                }
        }
    }

    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 (int const &i : bfs_order) /* 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 = 2; i < 3; --i)
        p[i] = (z % 3) - 1, z /= 3;
}

void decode(int n, int h)
{
    if (!h)
        return;
    vector<vector<int>> t(n), d(h, vector<int>(n));
    vector<int> p(n), bfs_order;
    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();
        t[p[i]].push_back(i);
    }

    queue<int> q;
    q.push(0);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int const &v : t[u])
            bfs_order.push_back(v), q.push(v);
    }
    assert(bfs_order.size() == n - 1);
    for (int const &i : bfs_order)
        hops(0, i, d[0][i] = d[0][p[i]] + 1);

    size_t l = 3;
    int c[3];
    for (int const &i : bfs_order)
        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:24:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   24 |     for (size_t i = 0; i < n; ++i)
      |                        ~~^~~
encoder.cpp:27:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   27 |     for (size_t i = 0; i < h; ++i)
      |                        ~~^~~
encoder.cpp:47:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   47 |     for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
      |                        ~~^~~
encoder.cpp:54:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   54 |         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)
      |                        ~~^~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from decoder.cpp:4:
decoder.cpp:39:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   39 |     assert(bfs_order.size() == n - 1);
      |            ~~~~~~~~~~~~~~~~~^~~~~~~~
decoder.cpp:46:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   46 |         for (size_t k = 1; k < h; ++k)
      |                            ~~^~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 10436 KB wrong parameter
2 Incorrect 3 ms 4472 KB wrong parameter
3 Incorrect 22 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4612 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 21 ms 5820 KB wrong parameter
7 Incorrect 39 ms 6040 KB wrong parameter
8 Incorrect 16 ms 5584 KB wrong parameter
9 Incorrect 18 ms 5748 KB wrong parameter
10 Incorrect 18 ms 5788 KB wrong parameter
11 Incorrect 22 ms 5880 KB wrong parameter
12 Incorrect 18 ms 5564 KB wrong parameter
13 Incorrect 42 ms 6080 KB wrong parameter
14 Incorrect 23 ms 5756 KB wrong parameter
15 Incorrect 18 ms 5788 KB wrong parameter
16 Incorrect 45 ms 6184 KB wrong parameter
17 Incorrect 34 ms 6164 KB wrong parameter
18 Incorrect 45 ms 6424 KB wrong parameter
19 Incorrect 33 ms 6044 KB wrong parameter
20 Incorrect 64 ms 6588 KB wrong parameter
21 Incorrect 70 ms 6680 KB wrong parameter
22 Incorrect 43 ms 6148 KB wrong parameter
23 Incorrect 84 ms 6916 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 10436 KB wrong parameter
2 Incorrect 3 ms 4472 KB wrong parameter
3 Incorrect 22 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4612 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 21 ms 5820 KB wrong parameter
7 Incorrect 39 ms 6040 KB wrong parameter
8 Incorrect 16 ms 5584 KB wrong parameter
9 Incorrect 18 ms 5748 KB wrong parameter
10 Incorrect 18 ms 5788 KB wrong parameter
11 Incorrect 22 ms 5880 KB wrong parameter
12 Incorrect 18 ms 5564 KB wrong parameter
13 Incorrect 42 ms 6080 KB wrong parameter
14 Incorrect 23 ms 5756 KB wrong parameter
15 Incorrect 18 ms 5788 KB wrong parameter
16 Incorrect 45 ms 6184 KB wrong parameter
17 Incorrect 34 ms 6164 KB wrong parameter
18 Incorrect 45 ms 6424 KB wrong parameter
19 Incorrect 33 ms 6044 KB wrong parameter
20 Incorrect 64 ms 6588 KB wrong parameter
21 Incorrect 70 ms 6680 KB wrong parameter
22 Incorrect 43 ms 6148 KB wrong parameter
23 Incorrect 84 ms 6916 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 10436 KB wrong parameter
2 Incorrect 3 ms 4472 KB wrong parameter
3 Incorrect 22 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4612 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 21 ms 5820 KB wrong parameter
7 Incorrect 39 ms 6040 KB wrong parameter
8 Incorrect 16 ms 5584 KB wrong parameter
9 Incorrect 18 ms 5748 KB wrong parameter
10 Incorrect 18 ms 5788 KB wrong parameter
11 Incorrect 22 ms 5880 KB wrong parameter
12 Incorrect 18 ms 5564 KB wrong parameter
13 Incorrect 42 ms 6080 KB wrong parameter
14 Incorrect 23 ms 5756 KB wrong parameter
15 Incorrect 18 ms 5788 KB wrong parameter
16 Incorrect 45 ms 6184 KB wrong parameter
17 Incorrect 34 ms 6164 KB wrong parameter
18 Incorrect 45 ms 6424 KB wrong parameter
19 Incorrect 33 ms 6044 KB wrong parameter
20 Incorrect 64 ms 6588 KB wrong parameter
21 Incorrect 70 ms 6680 KB wrong parameter
22 Incorrect 43 ms 6148 KB wrong parameter
23 Incorrect 84 ms 6916 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 274 ms 10436 KB wrong parameter
2 Incorrect 3 ms 4472 KB wrong parameter
3 Incorrect 22 ms 5352 KB wrong parameter
4 Incorrect 3 ms 4612 KB wrong parameter
5 Incorrect 24 ms 5688 KB wrong parameter
6 Incorrect 21 ms 5820 KB wrong parameter
7 Incorrect 39 ms 6040 KB wrong parameter
8 Incorrect 16 ms 5584 KB wrong parameter
9 Incorrect 18 ms 5748 KB wrong parameter
10 Incorrect 18 ms 5788 KB wrong parameter
11 Incorrect 22 ms 5880 KB wrong parameter
12 Incorrect 18 ms 5564 KB wrong parameter
13 Incorrect 42 ms 6080 KB wrong parameter
14 Incorrect 23 ms 5756 KB wrong parameter
15 Incorrect 18 ms 5788 KB wrong parameter
16 Incorrect 45 ms 6184 KB wrong parameter
17 Incorrect 34 ms 6164 KB wrong parameter
18 Incorrect 45 ms 6424 KB wrong parameter
19 Incorrect 33 ms 6044 KB wrong parameter
20 Incorrect 64 ms 6588 KB wrong parameter
21 Incorrect 70 ms 6680 KB wrong parameter
22 Incorrect 43 ms 6148 KB wrong parameter
23 Incorrect 84 ms 6916 KB wrong parameter