# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
597198 |
2022-07-15T17:18:27 Z |
Bench0310 |
Saveit (IOI10_saveit) |
C++17 |
|
222 ms |
10356 KB |
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
typedef long long ll;
void encode(int n,int h,int m,int *A,int *B)
{
vector<int> v[n];
for(int i=0;i<m;i++)
{
int a=A[i],b=B[i];
v[a].push_back(b);
v[b].push_back(a);
}
vector<int> g[n];
vector<int> p(n,-1);
function<void(int)> dfs=[&](int a)
{
for(int to:v[a])
{
if(p[to]!=-1) continue;
g[a].push_back(to);
g[to].push_back(a);
p[to]=a;
dfs(to);
}
};
p[0]=-2;
dfs(0);
for(int i=1;i<n;i++) for(int j=9;j>=0;j--) encode_bit((p[i]>>j)&1);
for(int i=0;i<h;i++)
{
queue<int> q;
vector<int> d(n,-1);
auto add=[&](int a,int nd)
{
if(d[a]==-1)
{
d[a]=nd;
q.push(a);
}
};
add(i,0);
while(!q.empty())
{
int a=q.front();
q.pop();
for(int to:v[a]) add(to,d[a]+1);
}
vector<int> x(n+2,0);
function<void(int,int)> go=[&](int a,int u)
{
if(u!=-1) x[a]=(d[a]-d[u]+1);
for(int to:g[a]) if(to!=u) go(to,a);
};
go(i,-1);
vector<int> y;
for(int j=0;j<n;j++) if(j!=i) y.push_back(x[j]);
for(int j=0;j<n-1;j+=3)
{
int t=(9*y[j]+3*y[j+1]+y[j+2]);
for(int k=4;k>=0;k--) encode_bit((t>>k)&1);
}
}
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
typedef long long ll;
void decode(int n,int h)
{
vector<int> v[n];
auto dec=[&](int c)->int
{
int t=0;
for(int i=0;i<c;i++) t=2*t+decode_bit();
return t;
};
for(int i=1;i<n;i++)
{
int p=dec(10);
v[i].push_back(p);
v[p].push_back(i);
}
for(int i=0;i<h;i++)
{
vector<int> x(n+2,0);
int pos=-1;
for(int j=0;j<n-1;j+=3)
{
int t=dec(5);
array<int,3> tmp={0,0,0};
for(int k=2;k>=0;k--)
{
tmp[k]=(t%3)-1;
t/=3;
}
for(int k=0;k<=2;k++)
{
pos++;
if(pos==i) pos++;
x[pos]=tmp[k];
}
}
vector<int> d(n,0);
function<void(int,int)> go=[&](int a,int p)
{
if(p!=-1) d[a]=d[p]+x[a];
hops(i,a,d[a]);
for(int to:v[a]) if(to!=p) go(to,a);
};
go(i,-1);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
10356 KB |
Output is correct - 69930 call(s) of encode_bit() |
2 |
Correct |
2 ms |
4604 KB |
Output is correct - 70 call(s) of encode_bit() |
3 |
Correct |
28 ms |
5492 KB |
Output is correct - 62990 call(s) of encode_bit() |
4 |
Correct |
2 ms |
4612 KB |
Output is correct - 90 call(s) of encode_bit() |
5 |
Correct |
24 ms |
5676 KB |
Output is correct - 62990 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5756 KB |
Output is correct - 69930 call(s) of encode_bit() |
7 |
Correct |
46 ms |
6224 KB |
Output is correct - 69930 call(s) of encode_bit() |
8 |
Correct |
25 ms |
5492 KB |
Output is correct - 67200 call(s) of encode_bit() |
9 |
Correct |
29 ms |
5468 KB |
Output is correct - 69930 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5504 KB |
Output is correct - 69930 call(s) of encode_bit() |
11 |
Correct |
26 ms |
5664 KB |
Output is correct - 69930 call(s) of encode_bit() |
12 |
Correct |
20 ms |
5628 KB |
Output is correct - 69930 call(s) of encode_bit() |
13 |
Correct |
49 ms |
6212 KB |
Output is correct - 69930 call(s) of encode_bit() |
14 |
Correct |
23 ms |
5712 KB |
Output is correct - 69930 call(s) of encode_bit() |
15 |
Correct |
25 ms |
5732 KB |
Output is correct - 69930 call(s) of encode_bit() |
16 |
Correct |
56 ms |
6144 KB |
Output is correct - 69930 call(s) of encode_bit() |
17 |
Correct |
36 ms |
6076 KB |
Output is correct - 69930 call(s) of encode_bit() |
18 |
Correct |
62 ms |
6176 KB |
Output is correct - 69930 call(s) of encode_bit() |
19 |
Correct |
36 ms |
5792 KB |
Output is correct - 69930 call(s) of encode_bit() |
20 |
Correct |
61 ms |
6456 KB |
Output is correct - 69930 call(s) of encode_bit() |
21 |
Correct |
89 ms |
6568 KB |
Output is correct - 69930 call(s) of encode_bit() |
22 |
Correct |
47 ms |
6172 KB |
Output is correct - 69930 call(s) of encode_bit() |
23 |
Correct |
81 ms |
6876 KB |
Output is correct - 69930 call(s) of encode_bit() |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
10356 KB |
Output is correct - 69930 call(s) of encode_bit() |
2 |
Correct |
2 ms |
4604 KB |
Output is correct - 70 call(s) of encode_bit() |
3 |
Correct |
28 ms |
5492 KB |
Output is correct - 62990 call(s) of encode_bit() |
4 |
Correct |
2 ms |
4612 KB |
Output is correct - 90 call(s) of encode_bit() |
5 |
Correct |
24 ms |
5676 KB |
Output is correct - 62990 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5756 KB |
Output is correct - 69930 call(s) of encode_bit() |
7 |
Correct |
46 ms |
6224 KB |
Output is correct - 69930 call(s) of encode_bit() |
8 |
Correct |
25 ms |
5492 KB |
Output is correct - 67200 call(s) of encode_bit() |
9 |
Correct |
29 ms |
5468 KB |
Output is correct - 69930 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5504 KB |
Output is correct - 69930 call(s) of encode_bit() |
11 |
Correct |
26 ms |
5664 KB |
Output is correct - 69930 call(s) of encode_bit() |
12 |
Correct |
20 ms |
5628 KB |
Output is correct - 69930 call(s) of encode_bit() |
13 |
Correct |
49 ms |
6212 KB |
Output is correct - 69930 call(s) of encode_bit() |
14 |
Correct |
23 ms |
5712 KB |
Output is correct - 69930 call(s) of encode_bit() |
15 |
Correct |
25 ms |
5732 KB |
Output is correct - 69930 call(s) of encode_bit() |
16 |
Correct |
56 ms |
6144 KB |
Output is correct - 69930 call(s) of encode_bit() |
17 |
Correct |
36 ms |
6076 KB |
Output is correct - 69930 call(s) of encode_bit() |
18 |
Correct |
62 ms |
6176 KB |
Output is correct - 69930 call(s) of encode_bit() |
19 |
Correct |
36 ms |
5792 KB |
Output is correct - 69930 call(s) of encode_bit() |
20 |
Correct |
61 ms |
6456 KB |
Output is correct - 69930 call(s) of encode_bit() |
21 |
Correct |
89 ms |
6568 KB |
Output is correct - 69930 call(s) of encode_bit() |
22 |
Correct |
47 ms |
6172 KB |
Output is correct - 69930 call(s) of encode_bit() |
23 |
Correct |
81 ms |
6876 KB |
Output is correct - 69930 call(s) of encode_bit() |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
10356 KB |
Output is correct - 69930 call(s) of encode_bit() |
2 |
Correct |
2 ms |
4604 KB |
Output is correct - 70 call(s) of encode_bit() |
3 |
Correct |
28 ms |
5492 KB |
Output is correct - 62990 call(s) of encode_bit() |
4 |
Correct |
2 ms |
4612 KB |
Output is correct - 90 call(s) of encode_bit() |
5 |
Correct |
24 ms |
5676 KB |
Output is correct - 62990 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5756 KB |
Output is correct - 69930 call(s) of encode_bit() |
7 |
Correct |
46 ms |
6224 KB |
Output is correct - 69930 call(s) of encode_bit() |
8 |
Correct |
25 ms |
5492 KB |
Output is correct - 67200 call(s) of encode_bit() |
9 |
Correct |
29 ms |
5468 KB |
Output is correct - 69930 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5504 KB |
Output is correct - 69930 call(s) of encode_bit() |
11 |
Correct |
26 ms |
5664 KB |
Output is correct - 69930 call(s) of encode_bit() |
12 |
Correct |
20 ms |
5628 KB |
Output is correct - 69930 call(s) of encode_bit() |
13 |
Correct |
49 ms |
6212 KB |
Output is correct - 69930 call(s) of encode_bit() |
14 |
Correct |
23 ms |
5712 KB |
Output is correct - 69930 call(s) of encode_bit() |
15 |
Correct |
25 ms |
5732 KB |
Output is correct - 69930 call(s) of encode_bit() |
16 |
Correct |
56 ms |
6144 KB |
Output is correct - 69930 call(s) of encode_bit() |
17 |
Correct |
36 ms |
6076 KB |
Output is correct - 69930 call(s) of encode_bit() |
18 |
Correct |
62 ms |
6176 KB |
Output is correct - 69930 call(s) of encode_bit() |
19 |
Correct |
36 ms |
5792 KB |
Output is correct - 69930 call(s) of encode_bit() |
20 |
Correct |
61 ms |
6456 KB |
Output is correct - 69930 call(s) of encode_bit() |
21 |
Correct |
89 ms |
6568 KB |
Output is correct - 69930 call(s) of encode_bit() |
22 |
Correct |
47 ms |
6172 KB |
Output is correct - 69930 call(s) of encode_bit() |
23 |
Correct |
81 ms |
6876 KB |
Output is correct - 69930 call(s) of encode_bit() |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
10356 KB |
Output is correct - 69930 call(s) of encode_bit() |
2 |
Correct |
2 ms |
4604 KB |
Output is correct - 70 call(s) of encode_bit() |
3 |
Correct |
28 ms |
5492 KB |
Output is correct - 62990 call(s) of encode_bit() |
4 |
Correct |
2 ms |
4612 KB |
Output is correct - 90 call(s) of encode_bit() |
5 |
Correct |
24 ms |
5676 KB |
Output is correct - 62990 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5756 KB |
Output is correct - 69930 call(s) of encode_bit() |
7 |
Correct |
46 ms |
6224 KB |
Output is correct - 69930 call(s) of encode_bit() |
8 |
Correct |
25 ms |
5492 KB |
Output is correct - 67200 call(s) of encode_bit() |
9 |
Correct |
29 ms |
5468 KB |
Output is correct - 69930 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5504 KB |
Output is correct - 69930 call(s) of encode_bit() |
11 |
Correct |
26 ms |
5664 KB |
Output is correct - 69930 call(s) of encode_bit() |
12 |
Correct |
20 ms |
5628 KB |
Output is correct - 69930 call(s) of encode_bit() |
13 |
Correct |
49 ms |
6212 KB |
Output is correct - 69930 call(s) of encode_bit() |
14 |
Correct |
23 ms |
5712 KB |
Output is correct - 69930 call(s) of encode_bit() |
15 |
Correct |
25 ms |
5732 KB |
Output is correct - 69930 call(s) of encode_bit() |
16 |
Correct |
56 ms |
6144 KB |
Output is correct - 69930 call(s) of encode_bit() |
17 |
Correct |
36 ms |
6076 KB |
Output is correct - 69930 call(s) of encode_bit() |
18 |
Correct |
62 ms |
6176 KB |
Output is correct - 69930 call(s) of encode_bit() |
19 |
Correct |
36 ms |
5792 KB |
Output is correct - 69930 call(s) of encode_bit() |
20 |
Correct |
61 ms |
6456 KB |
Output is correct - 69930 call(s) of encode_bit() |
21 |
Correct |
89 ms |
6568 KB |
Output is correct - 69930 call(s) of encode_bit() |
22 |
Correct |
47 ms |
6172 KB |
Output is correct - 69930 call(s) of encode_bit() |
23 |
Correct |
81 ms |
6876 KB |
Output is correct - 69930 call(s) of encode_bit() |