#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
const int N=1e3,H=36;
vector<int> e[N+10];
int d[H+2][N+10];
bool vis[N+10];
void send_int(int x)
{
for(int i=9;i>=0;i--)
encode_bit((x&(1<<i))!=0);
return;
}
void bfs(int n,int x)
{
for(int i=0;i<n;i++)
vis[i]=false;
queue<int> qq;
qq.push(x);
vis[x]=true;
d[x][x]=0;
while(!qq.empty())
{
int y=qq.front();
qq.pop();
//cerr<<"d "<<x<<" "<<y<<" "<<d[x][y]<<"\n";
for(auto v:e[y])
{
//cerr<<"e "<<x<<" "<<v<<"\n";
if(!vis[v])
{
vis[v]=true;
qq.push(v);
d[x][v]=d[x][y]+1;
}
}
}
return;
}
void send_weight(int x,int y,int h)
{
long long tmp=0;
for(int i=h-1;i>=0;i--)
tmp=3*tmp+1+d[i][y]-d[i][x];
//cerr<<x<<" "<<y<<" "<<tmp<<"\n";
for(int i=57;i>=0;i--)
encode_bit((tmp&(1LL<<i))!=0);
return;
}
void dfs(int x,int h)
{
//cerr<<"dfs_en "<<x<<"\n";
vis[x]=true;
for(auto v:e[x])
{
if(vis[v])
continue;
encode_bit(0);
send_int(v);
send_weight(x,v,h);
dfs(v,h);
}
encode_bit(1);
return;
}
void encode(int nv,int nh,int ne,int *v1,int *v2)
{
for(int i=0;i<ne;i++)
{
e[v1[i]].push_back(v2[i]);
e[v2[i]].push_back(v1[i]);
}
for(int i=0;i<nh;i++)
bfs(nv,i);
for(int i=0;i<nv;i++)
vis[i]=false;
dfs(0,nh);
encode_bit(1);
return;
}
#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
#define fi first
#define se second
using namespace std;
static const int N=1e3;
static vector<pair<int,long long>> e[N+10];
int receive_int()
{
int ans=0;
for(int i=0;i<10;i++)
ans=(2*ans+decode_bit());
return ans;
}
long long receive_weight()
{
long long ans=0;
for(int i=0;i<58;i++)
ans=(2*ans+decode_bit());
return ans;
}
long long reverse_weight(long long w,int h)
{
long long tmp=0;
for(int i=0;i<h;i++,w/=3)
tmp=3*tmp+2-w%3;
for(int i=0;i<h;i++,tmp/=3)
w=3*w+tmp%3;
return w;
}
static void dfs(int x,int h)
{
while(!decode_bit())
{
int y=receive_int();
long long w=receive_weight();
//cerr<<x<<" "<<y<<" "<<w<<"\n";
e[x].emplace_back(y,w);
e[y].emplace_back(x,reverse_weight(w,h));
dfs(y,h);
}
return;
}
static void dfs_ans(int x,int p,int h,int dd)
{
//cerr<<h<<" "<<x<<" "<<dd<<"\n";
hops(h,x,dd);
//cerr<<"ok\n";
for(auto &v:e[x])
{
//cerr<<x<<"("<<p<<")"<<" "<<v.fi<<" "<<v.se<<"\n";
if(v.fi!=p)
{
//cerr<<"ok\n";
dfs_ans(v.fi,x,h,dd+v.se%3-1);
//cerr<<"ok2\n";
}
v.se/=3;
}
return;
}
void decode(int nv,int nh)
{
dfs(0,nh);
for(int i=0;i<nh;i++)
dfs_ans(i,-1,i,0);
return;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
342 ms |
10376 KB |
Output is correct - 69932 call(s) of encode_bit() |
2 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
3 |
Correct |
24 ms |
5608 KB |
Output is correct - 62932 call(s) of encode_bit() |
4 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
5 |
Correct |
30 ms |
5756 KB |
Output is correct - 62932 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5788 KB |
Output is correct - 69932 call(s) of encode_bit() |
7 |
Correct |
48 ms |
6032 KB |
Output is correct - 69932 call(s) of encode_bit() |
8 |
Correct |
26 ms |
5548 KB |
Output is correct - 67202 call(s) of encode_bit() |
9 |
Correct |
27 ms |
5596 KB |
Output is correct - 69932 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5604 KB |
Output is correct - 69932 call(s) of encode_bit() |
11 |
Correct |
32 ms |
5748 KB |
Output is correct - 69932 call(s) of encode_bit() |
12 |
Correct |
27 ms |
5712 KB |
Output is correct - 69932 call(s) of encode_bit() |
13 |
Correct |
56 ms |
6304 KB |
Output is correct - 69932 call(s) of encode_bit() |
14 |
Correct |
28 ms |
5692 KB |
Output is correct - 69932 call(s) of encode_bit() |
15 |
Correct |
28 ms |
5716 KB |
Output is correct - 69932 call(s) of encode_bit() |
16 |
Correct |
54 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
17 |
Correct |
46 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
18 |
Correct |
72 ms |
6392 KB |
Output is correct - 69932 call(s) of encode_bit() |
19 |
Correct |
46 ms |
5956 KB |
Output is correct - 69932 call(s) of encode_bit() |
20 |
Correct |
60 ms |
6684 KB |
Output is correct - 69932 call(s) of encode_bit() |
21 |
Correct |
94 ms |
6860 KB |
Output is correct - 69932 call(s) of encode_bit() |
22 |
Correct |
63 ms |
6224 KB |
Output is correct - 69932 call(s) of encode_bit() |
23 |
Correct |
106 ms |
7000 KB |
Output is correct - 69932 call(s) of encode_bit() |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
342 ms |
10376 KB |
Output is correct - 69932 call(s) of encode_bit() |
2 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
3 |
Correct |
24 ms |
5608 KB |
Output is correct - 62932 call(s) of encode_bit() |
4 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
5 |
Correct |
30 ms |
5756 KB |
Output is correct - 62932 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5788 KB |
Output is correct - 69932 call(s) of encode_bit() |
7 |
Correct |
48 ms |
6032 KB |
Output is correct - 69932 call(s) of encode_bit() |
8 |
Correct |
26 ms |
5548 KB |
Output is correct - 67202 call(s) of encode_bit() |
9 |
Correct |
27 ms |
5596 KB |
Output is correct - 69932 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5604 KB |
Output is correct - 69932 call(s) of encode_bit() |
11 |
Correct |
32 ms |
5748 KB |
Output is correct - 69932 call(s) of encode_bit() |
12 |
Correct |
27 ms |
5712 KB |
Output is correct - 69932 call(s) of encode_bit() |
13 |
Correct |
56 ms |
6304 KB |
Output is correct - 69932 call(s) of encode_bit() |
14 |
Correct |
28 ms |
5692 KB |
Output is correct - 69932 call(s) of encode_bit() |
15 |
Correct |
28 ms |
5716 KB |
Output is correct - 69932 call(s) of encode_bit() |
16 |
Correct |
54 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
17 |
Correct |
46 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
18 |
Correct |
72 ms |
6392 KB |
Output is correct - 69932 call(s) of encode_bit() |
19 |
Correct |
46 ms |
5956 KB |
Output is correct - 69932 call(s) of encode_bit() |
20 |
Correct |
60 ms |
6684 KB |
Output is correct - 69932 call(s) of encode_bit() |
21 |
Correct |
94 ms |
6860 KB |
Output is correct - 69932 call(s) of encode_bit() |
22 |
Correct |
63 ms |
6224 KB |
Output is correct - 69932 call(s) of encode_bit() |
23 |
Correct |
106 ms |
7000 KB |
Output is correct - 69932 call(s) of encode_bit() |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
342 ms |
10376 KB |
Output is correct - 69932 call(s) of encode_bit() |
2 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
3 |
Correct |
24 ms |
5608 KB |
Output is correct - 62932 call(s) of encode_bit() |
4 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
5 |
Correct |
30 ms |
5756 KB |
Output is correct - 62932 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5788 KB |
Output is correct - 69932 call(s) of encode_bit() |
7 |
Correct |
48 ms |
6032 KB |
Output is correct - 69932 call(s) of encode_bit() |
8 |
Correct |
26 ms |
5548 KB |
Output is correct - 67202 call(s) of encode_bit() |
9 |
Correct |
27 ms |
5596 KB |
Output is correct - 69932 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5604 KB |
Output is correct - 69932 call(s) of encode_bit() |
11 |
Correct |
32 ms |
5748 KB |
Output is correct - 69932 call(s) of encode_bit() |
12 |
Correct |
27 ms |
5712 KB |
Output is correct - 69932 call(s) of encode_bit() |
13 |
Correct |
56 ms |
6304 KB |
Output is correct - 69932 call(s) of encode_bit() |
14 |
Correct |
28 ms |
5692 KB |
Output is correct - 69932 call(s) of encode_bit() |
15 |
Correct |
28 ms |
5716 KB |
Output is correct - 69932 call(s) of encode_bit() |
16 |
Correct |
54 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
17 |
Correct |
46 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
18 |
Correct |
72 ms |
6392 KB |
Output is correct - 69932 call(s) of encode_bit() |
19 |
Correct |
46 ms |
5956 KB |
Output is correct - 69932 call(s) of encode_bit() |
20 |
Correct |
60 ms |
6684 KB |
Output is correct - 69932 call(s) of encode_bit() |
21 |
Correct |
94 ms |
6860 KB |
Output is correct - 69932 call(s) of encode_bit() |
22 |
Correct |
63 ms |
6224 KB |
Output is correct - 69932 call(s) of encode_bit() |
23 |
Correct |
106 ms |
7000 KB |
Output is correct - 69932 call(s) of encode_bit() |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
342 ms |
10376 KB |
Output is correct - 69932 call(s) of encode_bit() |
2 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
3 |
Correct |
24 ms |
5608 KB |
Output is correct - 62932 call(s) of encode_bit() |
4 |
Correct |
3 ms |
4580 KB |
Output is correct - 282 call(s) of encode_bit() |
5 |
Correct |
30 ms |
5756 KB |
Output is correct - 62932 call(s) of encode_bit() |
6 |
Correct |
28 ms |
5788 KB |
Output is correct - 69932 call(s) of encode_bit() |
7 |
Correct |
48 ms |
6032 KB |
Output is correct - 69932 call(s) of encode_bit() |
8 |
Correct |
26 ms |
5548 KB |
Output is correct - 67202 call(s) of encode_bit() |
9 |
Correct |
27 ms |
5596 KB |
Output is correct - 69932 call(s) of encode_bit() |
10 |
Correct |
28 ms |
5604 KB |
Output is correct - 69932 call(s) of encode_bit() |
11 |
Correct |
32 ms |
5748 KB |
Output is correct - 69932 call(s) of encode_bit() |
12 |
Correct |
27 ms |
5712 KB |
Output is correct - 69932 call(s) of encode_bit() |
13 |
Correct |
56 ms |
6304 KB |
Output is correct - 69932 call(s) of encode_bit() |
14 |
Correct |
28 ms |
5692 KB |
Output is correct - 69932 call(s) of encode_bit() |
15 |
Correct |
28 ms |
5716 KB |
Output is correct - 69932 call(s) of encode_bit() |
16 |
Correct |
54 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
17 |
Correct |
46 ms |
6152 KB |
Output is correct - 69932 call(s) of encode_bit() |
18 |
Correct |
72 ms |
6392 KB |
Output is correct - 69932 call(s) of encode_bit() |
19 |
Correct |
46 ms |
5956 KB |
Output is correct - 69932 call(s) of encode_bit() |
20 |
Correct |
60 ms |
6684 KB |
Output is correct - 69932 call(s) of encode_bit() |
21 |
Correct |
94 ms |
6860 KB |
Output is correct - 69932 call(s) of encode_bit() |
22 |
Correct |
63 ms |
6224 KB |
Output is correct - 69932 call(s) of encode_bit() |
23 |
Correct |
106 ms |
7000 KB |
Output is correct - 69932 call(s) of encode_bit() |