| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 747197 |
2023-05-23T22:10:52 Z |
finn__ |
Saveit (IOI10_saveit) |
C++17 |
|
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 |
