| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 747200 |
2023-05-23T22:30:22 Z |
finn__ |
Saveit (IOI10_saveit) |
C++17 |
|
438 ms |
262144 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;
}
}
}
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);
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);
vector<int> bfs_order;
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);
}
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)
| ~~^~~
decoder.cpp:43:30: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
43 | for (size_t k = 1; k < h; ++k)
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
10264 KB |
duplicate hops call |
| 2 |
Incorrect |
2 ms |
4476 KB |
duplicate hops call |
| 3 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
3 ms |
4604 KB |
duplicate hops call |
| 5 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
382 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
358 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
349 ms |
262144 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
355 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
341 ms |
262144 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
414 ms |
262144 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
343 ms |
262144 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
364 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
395 ms |
262144 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
362 ms |
262144 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
388 ms |
262144 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
390 ms |
262144 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
399 ms |
262144 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
438 ms |
262144 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
402 ms |
262144 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
404 ms |
262144 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
10264 KB |
duplicate hops call |
| 2 |
Incorrect |
2 ms |
4476 KB |
duplicate hops call |
| 3 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
3 ms |
4604 KB |
duplicate hops call |
| 5 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
382 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
358 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
349 ms |
262144 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
355 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
341 ms |
262144 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
414 ms |
262144 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
343 ms |
262144 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
364 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
395 ms |
262144 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
362 ms |
262144 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
388 ms |
262144 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
390 ms |
262144 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
399 ms |
262144 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
438 ms |
262144 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
402 ms |
262144 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
404 ms |
262144 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
10264 KB |
duplicate hops call |
| 2 |
Incorrect |
2 ms |
4476 KB |
duplicate hops call |
| 3 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
3 ms |
4604 KB |
duplicate hops call |
| 5 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
382 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
358 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
349 ms |
262144 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
355 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
341 ms |
262144 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
414 ms |
262144 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
343 ms |
262144 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
364 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
395 ms |
262144 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
362 ms |
262144 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
388 ms |
262144 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
390 ms |
262144 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
399 ms |
262144 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
438 ms |
262144 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
402 ms |
262144 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
404 ms |
262144 KB |
Execution killed with signal 9 |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
172 ms |
10264 KB |
duplicate hops call |
| 2 |
Incorrect |
2 ms |
4476 KB |
duplicate hops call |
| 3 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 4 |
Incorrect |
3 ms |
4604 KB |
duplicate hops call |
| 5 |
Runtime error |
356 ms |
262144 KB |
Execution killed with signal 9 |
| 6 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 7 |
Runtime error |
382 ms |
262144 KB |
Execution killed with signal 9 |
| 8 |
Runtime error |
346 ms |
262144 KB |
Execution killed with signal 9 |
| 9 |
Runtime error |
358 ms |
262144 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
349 ms |
262144 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
355 ms |
262144 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
341 ms |
262144 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
414 ms |
262144 KB |
Execution killed with signal 9 |
| 14 |
Runtime error |
343 ms |
262144 KB |
Execution killed with signal 9 |
| 15 |
Runtime error |
364 ms |
262144 KB |
Execution killed with signal 9 |
| 16 |
Runtime error |
395 ms |
262144 KB |
Execution killed with signal 9 |
| 17 |
Runtime error |
362 ms |
262144 KB |
Execution killed with signal 9 |
| 18 |
Runtime error |
388 ms |
262144 KB |
Execution killed with signal 9 |
| 19 |
Runtime error |
390 ms |
262144 KB |
Execution killed with signal 9 |
| 20 |
Runtime error |
399 ms |
262144 KB |
Execution killed with signal 9 |
| 21 |
Runtime error |
438 ms |
262144 KB |
Execution killed with signal 9 |
| 22 |
Runtime error |
402 ms |
262144 KB |
Execution killed with signal 9 |
| 23 |
Runtime error |
404 ms |
262144 KB |
Execution killed with signal 9 |
