oj.uz

Submission #747198

# Submission time Handle Problem Language Result Execution time Memory
747198 2023-05-23T22:12:49 Z finn__ Saveit (IOI10_saveit) C++17
0 / 100
 286 ms 10412 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 = 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)
{
    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: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 = 1; 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 = 1; k < h; ++k)
      |                            ~~^~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 10412 KB wrong parameter
2 Incorrect 2 ms 4476 KB wrong parameter
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 21 ms 5560 KB wrong parameter
6 Incorrect 20 ms 5736 KB wrong parameter
7 Incorrect 44 ms 6060 KB wrong parameter
8 Incorrect 18 ms 5484 KB wrong parameter
9 Incorrect 19 ms 5648 KB wrong parameter
10 Incorrect 18 ms 5644 KB wrong parameter
11 Incorrect 22 ms 5680 KB wrong parameter
12 Incorrect 20 ms 5436 KB wrong parameter
13 Incorrect 40 ms 6196 KB wrong parameter
14 Incorrect 20 ms 5636 KB wrong parameter
15 Incorrect 21 ms 5672 KB wrong parameter
16 Incorrect 43 ms 6052 KB wrong parameter
17 Incorrect 34 ms 6128 KB wrong parameter
18 Incorrect 42 ms 6252 KB wrong parameter
19 Incorrect 28 ms 5780 KB wrong parameter
20 Incorrect 52 ms 6528 KB wrong parameter
21 Incorrect 76 ms 6712 KB wrong parameter
22 Incorrect 40 ms 6208 KB wrong parameter
23 Incorrect 63 ms 6900 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 10412 KB wrong parameter
2 Incorrect 2 ms 4476 KB wrong parameter
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 21 ms 5560 KB wrong parameter
6 Incorrect 20 ms 5736 KB wrong parameter
7 Incorrect 44 ms 6060 KB wrong parameter
8 Incorrect 18 ms 5484 KB wrong parameter
9 Incorrect 19 ms 5648 KB wrong parameter
10 Incorrect 18 ms 5644 KB wrong parameter
11 Incorrect 22 ms 5680 KB wrong parameter
12 Incorrect 20 ms 5436 KB wrong parameter
13 Incorrect 40 ms 6196 KB wrong parameter
14 Incorrect 20 ms 5636 KB wrong parameter
15 Incorrect 21 ms 5672 KB wrong parameter
16 Incorrect 43 ms 6052 KB wrong parameter
17 Incorrect 34 ms 6128 KB wrong parameter
18 Incorrect 42 ms 6252 KB wrong parameter
19 Incorrect 28 ms 5780 KB wrong parameter
20 Incorrect 52 ms 6528 KB wrong parameter
21 Incorrect 76 ms 6712 KB wrong parameter
22 Incorrect 40 ms 6208 KB wrong parameter
23 Incorrect 63 ms 6900 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 10412 KB wrong parameter
2 Incorrect 2 ms 4476 KB wrong parameter
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 21 ms 5560 KB wrong parameter
6 Incorrect 20 ms 5736 KB wrong parameter
7 Incorrect 44 ms 6060 KB wrong parameter
8 Incorrect 18 ms 5484 KB wrong parameter
9 Incorrect 19 ms 5648 KB wrong parameter
10 Incorrect 18 ms 5644 KB wrong parameter
11 Incorrect 22 ms 5680 KB wrong parameter
12 Incorrect 20 ms 5436 KB wrong parameter
13 Incorrect 40 ms 6196 KB wrong parameter
14 Incorrect 20 ms 5636 KB wrong parameter
15 Incorrect 21 ms 5672 KB wrong parameter
16 Incorrect 43 ms 6052 KB wrong parameter
17 Incorrect 34 ms 6128 KB wrong parameter
18 Incorrect 42 ms 6252 KB wrong parameter
19 Incorrect 28 ms 5780 KB wrong parameter
20 Incorrect 52 ms 6528 KB wrong parameter
21 Incorrect 76 ms 6712 KB wrong parameter
22 Incorrect 40 ms 6208 KB wrong parameter
23 Incorrect 63 ms 6900 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 286 ms 10412 KB wrong parameter
2 Incorrect 2 ms 4476 KB wrong parameter
3 Incorrect 22 ms 5480 KB wrong parameter
4 Incorrect 2 ms 4604 KB wrong parameter
5 Incorrect 21 ms 5560 KB wrong parameter
6 Incorrect 20 ms 5736 KB wrong parameter
7 Incorrect 44 ms 6060 KB wrong parameter
8 Incorrect 18 ms 5484 KB wrong parameter
9 Incorrect 19 ms 5648 KB wrong parameter
10 Incorrect 18 ms 5644 KB wrong parameter
11 Incorrect 22 ms 5680 KB wrong parameter
12 Incorrect 20 ms 5436 KB wrong parameter
13 Incorrect 40 ms 6196 KB wrong parameter
14 Incorrect 20 ms 5636 KB wrong parameter
15 Incorrect 21 ms 5672 KB wrong parameter
16 Incorrect 43 ms 6052 KB wrong parameter
17 Incorrect 34 ms 6128 KB wrong parameter
18 Incorrect 42 ms 6252 KB wrong parameter
19 Incorrect 28 ms 5780 KB wrong parameter
20 Incorrect 52 ms 6528 KB wrong parameter
21 Incorrect 76 ms 6712 KB wrong parameter
22 Incorrect 40 ms 6208 KB wrong parameter
23 Incorrect 63 ms 6900 KB wrong parameter