| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 566118 |
2022-05-21T20:19:03 Z |
RealSnake |
Saveit (IOI10_saveit) |
C++14 |
|
213 ms |
11940 KB |
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "encoder.h"
void encode(int n, int h, int p, int a[], int b[]) {
vector<int> v[n];
for(int i = 0; i < p; i++) {
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
set<int> s;
s.insert(0);
bool par[n] = {};
par[0] = 1;
vector<int> v2[n];
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
for(int i : v[x]) {
if(!par[i]) {
v2[x].push_back(i);
par[i] = x + 1;
s.insert(i);
}
}
sort(v[x].begin(), v[x].end());
}
for(int i = 0; i < n; i++) {
int x = par[i] - 1;
for(int j = 0; j < 10; j++)
encode_bit((x & (1 << j) > 0));
}
int ans[n][h];
for(int i = 0; i < n; i++) {
for(int j = 0; j < h; j++)
ans[i][j] = 1e9;
}
set<pair<int, pair<int, int>>> ss;
for(int i = 0; i < h; i++) {
ss.insert({0, {i, i}});
ans[i][i] = 0;
}
while(ss.size()) {
pair<int, pair<int, int>> p = *ss.begin();
ss.erase(ss.begin());
int x = p.second.first, hub = p.second.second;
int cost = p.first;
if(cost > ans[x][hub])
continue;
for(int i : v[x]) {
if(cost + 1 < ans[i][hub]) {
ans[i][hub] = cost + 1;
ss.insert({cost + 1, {i, hub}});
}
}
}
for(int i = 0; i < h; i++) {
int x = ans[0][i];
for(int j = 0; j < 10; j++)
encode_bit((x & (1 << j) > 0));
s.insert(0);
while(s.size()) {
x = *s.begin();
s.erase(s.begin());
for(int j : v2[x]) {
int dif = ans[j][i] - ans[x][i];
if(dif == 0)
encode_bit(0);
else {
encode_bit(1);
if(dif == 1)
encode_bit(1);
else
encode_bit(0);
}
}
}
}
}
#include "bits/stdc++.h"
using namespace std;
#include "grader.h"
#include "decoder.h"
void decode(int n, int h) {
vector<int> v[n];
for(int i = 0; i < n; i++) {
int x = 0;
for(int j = 0; j < 10; j++) {
if(decode_bit())
x += (1 << j);
}
if(i != x)
v[x].push_back(i);
}
for(int i = 0; i < h; i++) {
int b[n];
b[0] = 0;
for(int j = 0; j < 10; j++) {
if(decode_bit())
b[0] += (1 << j);
}
set<int> s;
s.insert(0);
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
hops(i, x, b[x]);
for(int j : v[x]) {
int dif = decode_bit();
if(dif) {
if(!decode_bit())
dif = -1;
}
b[j] = b[x] + dif;
s.insert(j);
}
}
}
}
Compilation message
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:32:38: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
32 | encode_bit((x & (1 << j) > 0));
| ~~~~~~~~~^~~
encoder.cpp:61:38: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
61 | encode_bit((x & (1 << j) > 0));
| ~~~~~~~~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
11940 KB |
wrong parameter |
| 2 |
Incorrect |
1 ms |
4488 KB |
wrong parameter |
| 3 |
Incorrect |
16 ms |
6256 KB |
too many decode_bit() calls |
| 4 |
Incorrect |
2 ms |
4608 KB |
wrong parameter |
| 5 |
Incorrect |
19 ms |
6912 KB |
wrong parameter |
| 6 |
Incorrect |
19 ms |
7020 KB |
too many decode_bit() calls |
| 7 |
Incorrect |
39 ms |
7664 KB |
wrong parameter |
| 8 |
Incorrect |
14 ms |
5252 KB |
too many decode_bit() calls |
| 9 |
Incorrect |
13 ms |
5256 KB |
too many decode_bit() calls |
| 10 |
Incorrect |
17 ms |
5316 KB |
wrong parameter |
| 11 |
Incorrect |
16 ms |
5436 KB |
too many decode_bit() calls |
| 12 |
Incorrect |
13 ms |
5116 KB |
too many decode_bit() calls |
| 13 |
Incorrect |
41 ms |
7084 KB |
wrong parameter |
| 14 |
Incorrect |
15 ms |
5240 KB |
too many decode_bit() calls |
| 15 |
Incorrect |
16 ms |
5236 KB |
wrong parameter |
| 16 |
Incorrect |
35 ms |
5668 KB |
too many decode_bit() calls |
| 17 |
Incorrect |
35 ms |
5880 KB |
wrong parameter |
| 18 |
Incorrect |
41 ms |
6248 KB |
wrong parameter |
| 19 |
Incorrect |
27 ms |
5996 KB |
wrong parameter |
| 20 |
Incorrect |
57 ms |
7196 KB |
too many decode_bit() calls |
| 21 |
Incorrect |
66 ms |
6976 KB |
wrong parameter |
| 22 |
Incorrect |
39 ms |
7472 KB |
wrong parameter |
| 23 |
Incorrect |
58 ms |
8100 KB |
too many decode_bit() calls |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
11940 KB |
wrong parameter |
| 2 |
Incorrect |
1 ms |
4488 KB |
wrong parameter |
| 3 |
Incorrect |
16 ms |
6256 KB |
too many decode_bit() calls |
| 4 |
Incorrect |
2 ms |
4608 KB |
wrong parameter |
| 5 |
Incorrect |
19 ms |
6912 KB |
wrong parameter |
| 6 |
Incorrect |
19 ms |
7020 KB |
too many decode_bit() calls |
| 7 |
Incorrect |
39 ms |
7664 KB |
wrong parameter |
| 8 |
Incorrect |
14 ms |
5252 KB |
too many decode_bit() calls |
| 9 |
Incorrect |
13 ms |
5256 KB |
too many decode_bit() calls |
| 10 |
Incorrect |
17 ms |
5316 KB |
wrong parameter |
| 11 |
Incorrect |
16 ms |
5436 KB |
too many decode_bit() calls |
| 12 |
Incorrect |
13 ms |
5116 KB |
too many decode_bit() calls |
| 13 |
Incorrect |
41 ms |
7084 KB |
wrong parameter |
| 14 |
Incorrect |
15 ms |
5240 KB |
too many decode_bit() calls |
| 15 |
Incorrect |
16 ms |
5236 KB |
wrong parameter |
| 16 |
Incorrect |
35 ms |
5668 KB |
too many decode_bit() calls |
| 17 |
Incorrect |
35 ms |
5880 KB |
wrong parameter |
| 18 |
Incorrect |
41 ms |
6248 KB |
wrong parameter |
| 19 |
Incorrect |
27 ms |
5996 KB |
wrong parameter |
| 20 |
Incorrect |
57 ms |
7196 KB |
too many decode_bit() calls |
| 21 |
Incorrect |
66 ms |
6976 KB |
wrong parameter |
| 22 |
Incorrect |
39 ms |
7472 KB |
wrong parameter |
| 23 |
Incorrect |
58 ms |
8100 KB |
too many decode_bit() calls |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
11940 KB |
wrong parameter |
| 2 |
Incorrect |
1 ms |
4488 KB |
wrong parameter |
| 3 |
Incorrect |
16 ms |
6256 KB |
too many decode_bit() calls |
| 4 |
Incorrect |
2 ms |
4608 KB |
wrong parameter |
| 5 |
Incorrect |
19 ms |
6912 KB |
wrong parameter |
| 6 |
Incorrect |
19 ms |
7020 KB |
too many decode_bit() calls |
| 7 |
Incorrect |
39 ms |
7664 KB |
wrong parameter |
| 8 |
Incorrect |
14 ms |
5252 KB |
too many decode_bit() calls |
| 9 |
Incorrect |
13 ms |
5256 KB |
too many decode_bit() calls |
| 10 |
Incorrect |
17 ms |
5316 KB |
wrong parameter |
| 11 |
Incorrect |
16 ms |
5436 KB |
too many decode_bit() calls |
| 12 |
Incorrect |
13 ms |
5116 KB |
too many decode_bit() calls |
| 13 |
Incorrect |
41 ms |
7084 KB |
wrong parameter |
| 14 |
Incorrect |
15 ms |
5240 KB |
too many decode_bit() calls |
| 15 |
Incorrect |
16 ms |
5236 KB |
wrong parameter |
| 16 |
Incorrect |
35 ms |
5668 KB |
too many decode_bit() calls |
| 17 |
Incorrect |
35 ms |
5880 KB |
wrong parameter |
| 18 |
Incorrect |
41 ms |
6248 KB |
wrong parameter |
| 19 |
Incorrect |
27 ms |
5996 KB |
wrong parameter |
| 20 |
Incorrect |
57 ms |
7196 KB |
too many decode_bit() calls |
| 21 |
Incorrect |
66 ms |
6976 KB |
wrong parameter |
| 22 |
Incorrect |
39 ms |
7472 KB |
wrong parameter |
| 23 |
Incorrect |
58 ms |
8100 KB |
too many decode_bit() calls |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
213 ms |
11940 KB |
wrong parameter |
| 2 |
Incorrect |
1 ms |
4488 KB |
wrong parameter |
| 3 |
Incorrect |
16 ms |
6256 KB |
too many decode_bit() calls |
| 4 |
Incorrect |
2 ms |
4608 KB |
wrong parameter |
| 5 |
Incorrect |
19 ms |
6912 KB |
wrong parameter |
| 6 |
Incorrect |
19 ms |
7020 KB |
too many decode_bit() calls |
| 7 |
Incorrect |
39 ms |
7664 KB |
wrong parameter |
| 8 |
Incorrect |
14 ms |
5252 KB |
too many decode_bit() calls |
| 9 |
Incorrect |
13 ms |
5256 KB |
too many decode_bit() calls |
| 10 |
Incorrect |
17 ms |
5316 KB |
wrong parameter |
| 11 |
Incorrect |
16 ms |
5436 KB |
too many decode_bit() calls |
| 12 |
Incorrect |
13 ms |
5116 KB |
too many decode_bit() calls |
| 13 |
Incorrect |
41 ms |
7084 KB |
wrong parameter |
| 14 |
Incorrect |
15 ms |
5240 KB |
too many decode_bit() calls |
| 15 |
Incorrect |
16 ms |
5236 KB |
wrong parameter |
| 16 |
Incorrect |
35 ms |
5668 KB |
too many decode_bit() calls |
| 17 |
Incorrect |
35 ms |
5880 KB |
wrong parameter |
| 18 |
Incorrect |
41 ms |
6248 KB |
wrong parameter |
| 19 |
Incorrect |
27 ms |
5996 KB |
wrong parameter |
| 20 |
Incorrect |
57 ms |
7196 KB |
too many decode_bit() calls |
| 21 |
Incorrect |
66 ms |
6976 KB |
wrong parameter |
| 22 |
Incorrect |
39 ms |
7472 KB |
wrong parameter |
| 23 |
Incorrect |
58 ms |
8100 KB |
too many decode_bit() calls |
