| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 747203 |
2023-05-23T22:56:38 Z |
finn__ |
Saveit (IOI10_saveit) |
C++17 |
|
165 ms |
6196 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);
}
}
}
assert(bfs_order.size() == n - 1);
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;
}
printf("%d\n", i);
}
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)
d[0][i] = d[0][p[i]] + 1, hops(0, i, d[0][i]);
for (size_t i = 1; i < h; ++i)
d[i][0] = d[0][i];
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]);
}
printf("%d\n", 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)
| ~~^~~
In file included from /usr/include/c++/10/cassert:44,
from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
from encoder.cpp:4:
encoder.cpp:47:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
47 | assert(bfs_order.size() == n - 1);
| ~~~~~~~~~~~~~~~~~^~~~~~~~
encoder.cpp:48:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
48 | for (size_t i = 1; i < n; ++i) /* encode bfs tree from 0 */
| ~~^~~
encoder.cpp:56:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
56 | 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:42:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
42 | for (size_t i = 1; i < h; ++i)
| ~~^~~
decoder.cpp:49:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
49 | for (size_t k = 1; k < h; ++k)
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
6196 KB |
Do not print anything to standard output: 1 |
| 2 |
Incorrect |
0 ms |
644 KB |
Do not print anything to standard output: 1 |
| 3 |
Incorrect |
12 ms |
1308 KB |
Do not print anything to standard output: 47 |
| 4 |
Incorrect |
1 ms |
648 KB |
Do not print anything to standard output: 1 |
| 5 |
Incorrect |
14 ms |
1404 KB |
Do not print anything to standard output: 28 |
| 6 |
Incorrect |
13 ms |
1396 KB |
Do not print anything to standard output: 40 |
| 7 |
Incorrect |
32 ms |
1592 KB |
Do not print anything to standard output: 10 |
| 8 |
Incorrect |
10 ms |
1156 KB |
Do not print anything to standard output: 108 |
| 9 |
Incorrect |
10 ms |
1284 KB |
Do not print anything to standard output: 559 |
| 10 |
Incorrect |
11 ms |
1316 KB |
Do not print anything to standard output: 7 |
| 11 |
Incorrect |
17 ms |
1424 KB |
Do not print anything to standard output: 364 |
| 12 |
Incorrect |
11 ms |
1252 KB |
Do not print anything to standard output: 103 |
| 13 |
Incorrect |
32 ms |
1820 KB |
Do not print anything to standard output: 1 |
| 14 |
Incorrect |
11 ms |
1300 KB |
Do not print anything to standard output: 468 |
| 15 |
Incorrect |
11 ms |
1364 KB |
Do not print anything to standard output: 12 |
| 16 |
Incorrect |
41 ms |
1712 KB |
Do not print anything to standard output: 12 |
| 17 |
Incorrect |
24 ms |
1660 KB |
Do not print anything to standard output: 11 |
| 18 |
Incorrect |
47 ms |
1880 KB |
Do not print anything to standard output: 1 |
| 19 |
Incorrect |
27 ms |
1552 KB |
Do not print anything to standard output: 16 |
| 20 |
Incorrect |
46 ms |
2240 KB |
Do not print anything to standard output: 52 |
| 21 |
Incorrect |
54 ms |
2272 KB |
Do not print anything to standard output: 3 |
| 22 |
Incorrect |
39 ms |
1868 KB |
Do not print anything to standard output: 22 |
| 23 |
Incorrect |
53 ms |
2588 KB |
Do not print anything to standard output: 83 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
6196 KB |
Do not print anything to standard output: 1 |
| 2 |
Incorrect |
0 ms |
644 KB |
Do not print anything to standard output: 1 |
| 3 |
Incorrect |
12 ms |
1308 KB |
Do not print anything to standard output: 47 |
| 4 |
Incorrect |
1 ms |
648 KB |
Do not print anything to standard output: 1 |
| 5 |
Incorrect |
14 ms |
1404 KB |
Do not print anything to standard output: 28 |
| 6 |
Incorrect |
13 ms |
1396 KB |
Do not print anything to standard output: 40 |
| 7 |
Incorrect |
32 ms |
1592 KB |
Do not print anything to standard output: 10 |
| 8 |
Incorrect |
10 ms |
1156 KB |
Do not print anything to standard output: 108 |
| 9 |
Incorrect |
10 ms |
1284 KB |
Do not print anything to standard output: 559 |
| 10 |
Incorrect |
11 ms |
1316 KB |
Do not print anything to standard output: 7 |
| 11 |
Incorrect |
17 ms |
1424 KB |
Do not print anything to standard output: 364 |
| 12 |
Incorrect |
11 ms |
1252 KB |
Do not print anything to standard output: 103 |
| 13 |
Incorrect |
32 ms |
1820 KB |
Do not print anything to standard output: 1 |
| 14 |
Incorrect |
11 ms |
1300 KB |
Do not print anything to standard output: 468 |
| 15 |
Incorrect |
11 ms |
1364 KB |
Do not print anything to standard output: 12 |
| 16 |
Incorrect |
41 ms |
1712 KB |
Do not print anything to standard output: 12 |
| 17 |
Incorrect |
24 ms |
1660 KB |
Do not print anything to standard output: 11 |
| 18 |
Incorrect |
47 ms |
1880 KB |
Do not print anything to standard output: 1 |
| 19 |
Incorrect |
27 ms |
1552 KB |
Do not print anything to standard output: 16 |
| 20 |
Incorrect |
46 ms |
2240 KB |
Do not print anything to standard output: 52 |
| 21 |
Incorrect |
54 ms |
2272 KB |
Do not print anything to standard output: 3 |
| 22 |
Incorrect |
39 ms |
1868 KB |
Do not print anything to standard output: 22 |
| 23 |
Incorrect |
53 ms |
2588 KB |
Do not print anything to standard output: 83 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
6196 KB |
Do not print anything to standard output: 1 |
| 2 |
Incorrect |
0 ms |
644 KB |
Do not print anything to standard output: 1 |
| 3 |
Incorrect |
12 ms |
1308 KB |
Do not print anything to standard output: 47 |
| 4 |
Incorrect |
1 ms |
648 KB |
Do not print anything to standard output: 1 |
| 5 |
Incorrect |
14 ms |
1404 KB |
Do not print anything to standard output: 28 |
| 6 |
Incorrect |
13 ms |
1396 KB |
Do not print anything to standard output: 40 |
| 7 |
Incorrect |
32 ms |
1592 KB |
Do not print anything to standard output: 10 |
| 8 |
Incorrect |
10 ms |
1156 KB |
Do not print anything to standard output: 108 |
| 9 |
Incorrect |
10 ms |
1284 KB |
Do not print anything to standard output: 559 |
| 10 |
Incorrect |
11 ms |
1316 KB |
Do not print anything to standard output: 7 |
| 11 |
Incorrect |
17 ms |
1424 KB |
Do not print anything to standard output: 364 |
| 12 |
Incorrect |
11 ms |
1252 KB |
Do not print anything to standard output: 103 |
| 13 |
Incorrect |
32 ms |
1820 KB |
Do not print anything to standard output: 1 |
| 14 |
Incorrect |
11 ms |
1300 KB |
Do not print anything to standard output: 468 |
| 15 |
Incorrect |
11 ms |
1364 KB |
Do not print anything to standard output: 12 |
| 16 |
Incorrect |
41 ms |
1712 KB |
Do not print anything to standard output: 12 |
| 17 |
Incorrect |
24 ms |
1660 KB |
Do not print anything to standard output: 11 |
| 18 |
Incorrect |
47 ms |
1880 KB |
Do not print anything to standard output: 1 |
| 19 |
Incorrect |
27 ms |
1552 KB |
Do not print anything to standard output: 16 |
| 20 |
Incorrect |
46 ms |
2240 KB |
Do not print anything to standard output: 52 |
| 21 |
Incorrect |
54 ms |
2272 KB |
Do not print anything to standard output: 3 |
| 22 |
Incorrect |
39 ms |
1868 KB |
Do not print anything to standard output: 22 |
| 23 |
Incorrect |
53 ms |
2588 KB |
Do not print anything to standard output: 83 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
165 ms |
6196 KB |
Do not print anything to standard output: 1 |
| 2 |
Incorrect |
0 ms |
644 KB |
Do not print anything to standard output: 1 |
| 3 |
Incorrect |
12 ms |
1308 KB |
Do not print anything to standard output: 47 |
| 4 |
Incorrect |
1 ms |
648 KB |
Do not print anything to standard output: 1 |
| 5 |
Incorrect |
14 ms |
1404 KB |
Do not print anything to standard output: 28 |
| 6 |
Incorrect |
13 ms |
1396 KB |
Do not print anything to standard output: 40 |
| 7 |
Incorrect |
32 ms |
1592 KB |
Do not print anything to standard output: 10 |
| 8 |
Incorrect |
10 ms |
1156 KB |
Do not print anything to standard output: 108 |
| 9 |
Incorrect |
10 ms |
1284 KB |
Do not print anything to standard output: 559 |
| 10 |
Incorrect |
11 ms |
1316 KB |
Do not print anything to standard output: 7 |
| 11 |
Incorrect |
17 ms |
1424 KB |
Do not print anything to standard output: 364 |
| 12 |
Incorrect |
11 ms |
1252 KB |
Do not print anything to standard output: 103 |
| 13 |
Incorrect |
32 ms |
1820 KB |
Do not print anything to standard output: 1 |
| 14 |
Incorrect |
11 ms |
1300 KB |
Do not print anything to standard output: 468 |
| 15 |
Incorrect |
11 ms |
1364 KB |
Do not print anything to standard output: 12 |
| 16 |
Incorrect |
41 ms |
1712 KB |
Do not print anything to standard output: 12 |
| 17 |
Incorrect |
24 ms |
1660 KB |
Do not print anything to standard output: 11 |
| 18 |
Incorrect |
47 ms |
1880 KB |
Do not print anything to standard output: 1 |
| 19 |
Incorrect |
27 ms |
1552 KB |
Do not print anything to standard output: 16 |
| 20 |
Incorrect |
46 ms |
2240 KB |
Do not print anything to standard output: 52 |
| 21 |
Incorrect |
54 ms |
2272 KB |
Do not print anything to standard output: 3 |
| 22 |
Incorrect |
39 ms |
1868 KB |
Do not print anything to standard output: 22 |
| 23 |
Incorrect |
53 ms |
2588 KB |
Do not print anything to standard output: 83 |
