| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 566650 |
2022-05-22T14:10:21 Z |
RealSnake |
Saveit (IOI10_saveit) |
C++14 |
|
216 ms |
16132 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);
int 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);
v2[i].push_back(x);
par[i] = x + 1;
s.insert(i);
}
}
}
for(int i = 0; i < n; i++)
sort(v2[i].begin(), v2[i].end());
for(int i = 1; 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}});
}
}
}
bool vis[n];
for(int i = 1; i < h; i++) {
for(int j = 0; j < n; j++)
vis[j] = 0;
s.insert(i);
vis[i] = 1;
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
for(int j : v2[x]) {
if(vis[j])
continue;
vis[j] = 1;
s.insert(j);
if(j <= i)
continue;
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 = 1; i < n; i++) {
int x = 0;
for(int j = 0; j < 10; j++) {
if(decode_bit())
x += (1 << j);
}
v[x].push_back(i);
v[i].push_back(x);
}
for(int i = 0; i < n; i++)
sort(v[i].begin(), v[i].end());
int ans[n][n];
bool vis[n] = {};
set<int> s;
s.insert(0);
ans[0][0] = 0;
vis[0] = 1;
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
hops(0, x, ans[x][0]);
if(x < h && x != 0)
hops(x, 0, ans[x][0]);
for(int i : v[x]) {
if(vis[i])
continue;
vis[i] = 1;
ans[i][0] = ans[0][i] = ans[x][0] + 1;
s.insert(i);
}
}
for(int i = 1; i < h; i++) {
for(int j = 0; j < n; j++)
vis[j] = 0;
ans[i][i] = 0;
s.insert(i);
vis[i] = 1;
while(s.size()) {
int x = *s.begin();
s.erase(s.begin());
if(x >= i) {
hops(i, x, ans[x][i]);
if(x < h && x != i)
hops(x, i, ans[x][i]);
}
for(int j : v[x]) {
if(vis[j])
continue;
vis[j] = 1;
s.insert(j);
if(j <= i)
continue;
int dif = decode_bit();
if(dif) {
if(!decode_bit())
dif = -1;
}
ans[j][i] = ans[i][j] = ans[x][i] + dif;
}
}
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
16132 KB |
Output isn't correct |
| 2 |
Correct |
2 ms |
4476 KB |
Output is correct - 47 call(s) of encode_bit() |
| 3 |
Incorrect |
36 ms |
9896 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
4604 KB |
Output is correct - 47 call(s) of encode_bit() |
| 5 |
Incorrect |
39 ms |
10436 KB |
Output isn't correct |
| 6 |
Incorrect |
40 ms |
11348 KB |
Output isn't correct |
| 7 |
Incorrect |
59 ms |
11876 KB |
Output isn't correct |
| 8 |
Incorrect |
47 ms |
9352 KB |
Output isn't correct |
| 9 |
Incorrect |
40 ms |
9636 KB |
Output isn't correct |
| 10 |
Correct |
34 ms |
9660 KB |
Output is partially correct - 77065 call(s) of encode_bit() |
| 11 |
Incorrect |
44 ms |
9844 KB |
Output isn't correct |
| 12 |
Correct |
33 ms |
9604 KB |
Output is partially correct - 78660 call(s) of encode_bit() |
| 13 |
Incorrect |
57 ms |
11344 KB |
Output isn't correct |
| 14 |
Incorrect |
38 ms |
9592 KB |
Output isn't correct |
| 15 |
Incorrect |
35 ms |
9692 KB |
Output isn't correct |
| 16 |
Incorrect |
55 ms |
10220 KB |
Output isn't correct |
| 17 |
Incorrect |
53 ms |
10120 KB |
Output isn't correct |
| 18 |
Incorrect |
59 ms |
10604 KB |
Output isn't correct |
| 19 |
Incorrect |
48 ms |
10264 KB |
Output isn't correct |
| 20 |
Incorrect |
70 ms |
11608 KB |
Output isn't correct |
| 21 |
Incorrect |
79 ms |
11332 KB |
Output isn't correct |
| 22 |
Incorrect |
67 ms |
11804 KB |
Output isn't correct |
| 23 |
Incorrect |
83 ms |
12500 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
16132 KB |
Output isn't correct |
| 2 |
Correct |
2 ms |
4476 KB |
Output is correct - 47 call(s) of encode_bit() |
| 3 |
Incorrect |
36 ms |
9896 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
4604 KB |
Output is correct - 47 call(s) of encode_bit() |
| 5 |
Incorrect |
39 ms |
10436 KB |
Output isn't correct |
| 6 |
Incorrect |
40 ms |
11348 KB |
Output isn't correct |
| 7 |
Incorrect |
59 ms |
11876 KB |
Output isn't correct |
| 8 |
Incorrect |
47 ms |
9352 KB |
Output isn't correct |
| 9 |
Incorrect |
40 ms |
9636 KB |
Output isn't correct |
| 10 |
Correct |
34 ms |
9660 KB |
Output is partially correct - 77065 call(s) of encode_bit() |
| 11 |
Incorrect |
44 ms |
9844 KB |
Output isn't correct |
| 12 |
Correct |
33 ms |
9604 KB |
Output is partially correct - 78660 call(s) of encode_bit() |
| 13 |
Incorrect |
57 ms |
11344 KB |
Output isn't correct |
| 14 |
Incorrect |
38 ms |
9592 KB |
Output isn't correct |
| 15 |
Incorrect |
35 ms |
9692 KB |
Output isn't correct |
| 16 |
Incorrect |
55 ms |
10220 KB |
Output isn't correct |
| 17 |
Incorrect |
53 ms |
10120 KB |
Output isn't correct |
| 18 |
Incorrect |
59 ms |
10604 KB |
Output isn't correct |
| 19 |
Incorrect |
48 ms |
10264 KB |
Output isn't correct |
| 20 |
Incorrect |
70 ms |
11608 KB |
Output isn't correct |
| 21 |
Incorrect |
79 ms |
11332 KB |
Output isn't correct |
| 22 |
Incorrect |
67 ms |
11804 KB |
Output isn't correct |
| 23 |
Incorrect |
83 ms |
12500 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
16132 KB |
Output isn't correct |
| 2 |
Correct |
2 ms |
4476 KB |
Output is correct - 47 call(s) of encode_bit() |
| 3 |
Incorrect |
36 ms |
9896 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
4604 KB |
Output is correct - 47 call(s) of encode_bit() |
| 5 |
Incorrect |
39 ms |
10436 KB |
Output isn't correct |
| 6 |
Incorrect |
40 ms |
11348 KB |
Output isn't correct |
| 7 |
Incorrect |
59 ms |
11876 KB |
Output isn't correct |
| 8 |
Incorrect |
47 ms |
9352 KB |
Output isn't correct |
| 9 |
Incorrect |
40 ms |
9636 KB |
Output isn't correct |
| 10 |
Correct |
34 ms |
9660 KB |
Output is partially correct - 77065 call(s) of encode_bit() |
| 11 |
Incorrect |
44 ms |
9844 KB |
Output isn't correct |
| 12 |
Correct |
33 ms |
9604 KB |
Output is partially correct - 78660 call(s) of encode_bit() |
| 13 |
Incorrect |
57 ms |
11344 KB |
Output isn't correct |
| 14 |
Incorrect |
38 ms |
9592 KB |
Output isn't correct |
| 15 |
Incorrect |
35 ms |
9692 KB |
Output isn't correct |
| 16 |
Incorrect |
55 ms |
10220 KB |
Output isn't correct |
| 17 |
Incorrect |
53 ms |
10120 KB |
Output isn't correct |
| 18 |
Incorrect |
59 ms |
10604 KB |
Output isn't correct |
| 19 |
Incorrect |
48 ms |
10264 KB |
Output isn't correct |
| 20 |
Incorrect |
70 ms |
11608 KB |
Output isn't correct |
| 21 |
Incorrect |
79 ms |
11332 KB |
Output isn't correct |
| 22 |
Incorrect |
67 ms |
11804 KB |
Output isn't correct |
| 23 |
Incorrect |
83 ms |
12500 KB |
Output isn't correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
216 ms |
16132 KB |
Output isn't correct |
| 2 |
Correct |
2 ms |
4476 KB |
Output is correct - 47 call(s) of encode_bit() |
| 3 |
Incorrect |
36 ms |
9896 KB |
Output isn't correct |
| 4 |
Correct |
2 ms |
4604 KB |
Output is correct - 47 call(s) of encode_bit() |
| 5 |
Incorrect |
39 ms |
10436 KB |
Output isn't correct |
| 6 |
Incorrect |
40 ms |
11348 KB |
Output isn't correct |
| 7 |
Incorrect |
59 ms |
11876 KB |
Output isn't correct |
| 8 |
Incorrect |
47 ms |
9352 KB |
Output isn't correct |
| 9 |
Incorrect |
40 ms |
9636 KB |
Output isn't correct |
| 10 |
Correct |
34 ms |
9660 KB |
Output is partially correct - 77065 call(s) of encode_bit() |
| 11 |
Incorrect |
44 ms |
9844 KB |
Output isn't correct |
| 12 |
Correct |
33 ms |
9604 KB |
Output is partially correct - 78660 call(s) of encode_bit() |
| 13 |
Incorrect |
57 ms |
11344 KB |
Output isn't correct |
| 14 |
Incorrect |
38 ms |
9592 KB |
Output isn't correct |
| 15 |
Incorrect |
35 ms |
9692 KB |
Output isn't correct |
| 16 |
Incorrect |
55 ms |
10220 KB |
Output isn't correct |
| 17 |
Incorrect |
53 ms |
10120 KB |
Output isn't correct |
| 18 |
Incorrect |
59 ms |
10604 KB |
Output isn't correct |
| 19 |
Incorrect |
48 ms |
10264 KB |
Output isn't correct |
| 20 |
Incorrect |
70 ms |
11608 KB |
Output isn't correct |
| 21 |
Incorrect |
79 ms |
11332 KB |
Output isn't correct |
| 22 |
Incorrect |
67 ms |
11804 KB |
Output isn't correct |
| 23 |
Incorrect |
83 ms |
12500 KB |
Output isn't correct |
