| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 534023 |
2022-03-07T19:55:15 Z |
sidon |
Saveit (IOI10_saveit) |
C++17 |
|
242 ms |
10688 KB |
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "encoder.h"
const int Z = 1000;
int p[Z], d[Z];
bool vis[Z];
vector<int> g[Z];
void dfs(int u) {
vis[u] = 1;
for(const int &v : g[u]) if(!vis[v]) {
dfs(v);
p[v] = u;
}
}
void encode(int n, int h, int m, int *a, int *b) {
for(int i = 0; i < m; ++i) {
g[a[i]].push_back(b[i]);
g[b[i]].push_back(a[i]);
}
dfs(0);
for(int i = 1; i < n; ++i)
for(int j = 0; j < 10; ++j)
encode_bit(bool(p[i] & (1<<j)));
vector<int> x;
for(int r = 0; r < h; ++r) {
queue<int> q;
fill(d, d + n, -1);
q.push(r);
d[r] = 0;
while(!empty(q)) {
int u = q.front(); q.pop();
for(const int &v : g[u]) if(d[v] < 0)
d[v] = d[u] + 1, q.push(v);
}
for(int u = 1; u < n; ++u)
x.push_back(1 + d[u] - d[p[u]]);
}
while(size(x) % 3) x.push_back(0);
for(int i = 0; i < int(size(x)); i += 3) {
int num = x[i] + x[i + 1] * 3 + x[i + 2] * 9;
for(int j = 0; j < 5; ++j)
encode_bit(bool(num & (1<<j)));
}
return;
}
#include <bits/stdc++.h>
using namespace std;
#include "grader.h"
#include "decoder.h"
const int Z = 1000;
int p[Z], w[Z], r;
vector<int> g[Z], x;
void dfs(int u, int par, int d) {
hops(r, u, d);
for(const int &v : g[u]) if(v != par)
dfs(v, u, d + (u == p[v] ? w[v] : -w[u]));
}
void decode(int n, int h) {
for(int i = 1; i < n; ++i) {
for(int j = 0; j < 10; ++j)
if(decode_bit()) p[i] |= 1<<j;
g[i].push_back(p[i]);
g[p[i]].push_back(i);
}
x.resize(n * h - h);
while(size(x) % 3) x.push_back(0);
for(int i = 0; i < int(size(x)); i += 3) {
int num {};
for(int j = 0; j < 5; ++j)
if(decode_bit()) num |= 1<<j;
for(int j = 0; j < 3; ++j, num /= 3)
x[i + j] = (num % 3) - 1;
}
for(int pt = r = 0; r < h; ++r) {
for(int u = 1; u < n; ++u)
w[u] = x[pt++];
dfs(r, r, 0);
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
10688 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4588 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
24 ms |
5800 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4588 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
5960 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
35 ms |
5972 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
44 ms |
6232 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5864 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
26 ms |
5996 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
24 ms |
5988 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
32 ms |
5892 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
23 ms |
6008 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
66 ms |
6416 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
28 ms |
6032 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
6088 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
61 ms |
6420 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
45 ms |
6444 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
54 ms |
6536 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
37 ms |
6136 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
83 ms |
6932 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
86 ms |
6956 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
56 ms |
6480 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
81 ms |
7212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
10688 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4588 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
24 ms |
5800 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4588 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
5960 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
35 ms |
5972 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
44 ms |
6232 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5864 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
26 ms |
5996 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
24 ms |
5988 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
32 ms |
5892 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
23 ms |
6008 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
66 ms |
6416 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
28 ms |
6032 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
6088 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
61 ms |
6420 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
45 ms |
6444 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
54 ms |
6536 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
37 ms |
6136 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
83 ms |
6932 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
86 ms |
6956 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
56 ms |
6480 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
81 ms |
7212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
10688 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4588 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
24 ms |
5800 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4588 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
5960 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
35 ms |
5972 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
44 ms |
6232 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5864 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
26 ms |
5996 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
24 ms |
5988 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
32 ms |
5892 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
23 ms |
6008 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
66 ms |
6416 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
28 ms |
6032 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
6088 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
61 ms |
6420 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
45 ms |
6444 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
54 ms |
6536 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
37 ms |
6136 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
83 ms |
6932 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
86 ms |
6956 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
56 ms |
6480 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
81 ms |
7212 KB |
Output is correct - 69930 call(s) of encode_bit() |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
242 ms |
10688 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 2 |
Correct |
2 ms |
4588 KB |
Output is correct - 60 call(s) of encode_bit() |
| 3 |
Correct |
24 ms |
5800 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 4 |
Correct |
2 ms |
4588 KB |
Output is correct - 75 call(s) of encode_bit() |
| 5 |
Correct |
27 ms |
5960 KB |
Output is correct - 62930 call(s) of encode_bit() |
| 6 |
Correct |
35 ms |
5972 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 7 |
Correct |
44 ms |
6232 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 8 |
Correct |
23 ms |
5864 KB |
Output is correct - 67200 call(s) of encode_bit() |
| 9 |
Correct |
26 ms |
5996 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 10 |
Correct |
24 ms |
5988 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 11 |
Correct |
32 ms |
5892 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 12 |
Correct |
23 ms |
6008 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 13 |
Correct |
66 ms |
6416 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 14 |
Correct |
28 ms |
6032 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 15 |
Correct |
31 ms |
6088 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 16 |
Correct |
61 ms |
6420 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 17 |
Correct |
45 ms |
6444 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 18 |
Correct |
54 ms |
6536 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 19 |
Correct |
37 ms |
6136 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 20 |
Correct |
83 ms |
6932 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 21 |
Correct |
86 ms |
6956 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 22 |
Correct |
56 ms |
6480 KB |
Output is correct - 69930 call(s) of encode_bit() |
| 23 |
Correct |
81 ms |
7212 KB |
Output is correct - 69930 call(s) of encode_bit() |
