#include "grader.h"
#include "encoder.h"
#include <vector>
#include <queue>
using namespace std;
static queue <int> Q;
static vector <int> A[1000];
static int nv, nh, ne, Anc[1000], Check[1000], D[36][1000];
void static MakeAnc(void) {
int i, j, Now;
Q.push(0);
Check[0]=1;
while(!Q.empty()) {
Now=Q.front();
Q.pop();
j=A[Now].size();
for(i=0 ; i<j ; i++)
if(!Check[A[Now][i]]) {
Check[A[Now][i]]=1;
Anc[A[Now][i]]=Now;
Q.push(A[Now][i]);
}
}
}
void static BFS(int S) {
int i, j, Now;
for(i=0 ; i<nv ; i++)
Check[i]=0;
Check[S]=1;
D[S][S]=0;
Q.push(S);
while(!Q.empty()) {
Now=Q.front();
Q.pop();
j=A[Now].size();
for(i=0 ; i<j ; i++)
if(!Check[A[Now][i]]) {
Check[A[Now][i]]=1;
D[S][A[Now][i]]=D[S][Now]+1;
Q.push(A[Now][i]);
}
}
}
void static Send(int X) {
int i;
for(i=0 ; i<8 ; i++) {
if(X&(1<<i))
encode_bit(1);
else
encode_bit(0);
}
}
void encode(int nv_, int nh_, int ne_, int *v1, int *v2) {
int i, j, Temp1, Temp2, Cnt;
nv=nv_;
nh=nh_;
ne=ne_;
for(i=0 ; i<ne ; i++) {
A[v1[i]].push_back(v2[i]);
A[v2[i]].push_back(v1[i]);
}
MakeAnc();
for(i=1 ; i<nv ; i++) {
Temp1=Anc[i];
for(j=0 ; j<10 ; j++) {
if(Temp1&(1<<j))
encode_bit(1);
else
encode_bit(0);
}
}
for(i=0 ; i<nh ; i++)
BFS(i);
for(i=1 ; i<nv ; i++) {
Temp1=Cnt=0;
Temp2=1;
for(j=0 ; j<nh ; j++) {
Cnt++;
if(D[j][i]-D[j][Anc[i]]==1)
Temp1+=2*Temp2;
else if(D[j][i]-D[j][Anc[i]]==0)
Temp1+=Temp2;
Temp2*=3;
if(!(Cnt%5)) {
Send(Temp1);
Temp1=0;
Temp2=1;
}
}
if(Cnt%5)
Send(Temp1);
}
}
#include "grader.h"
#include "decoder.h"
#include <vector>
#include <queue>
using namespace std;
static vector <int> A[1000];
static queue <int> Q;
static int nv, nh, Anc[1000], D[36][1000], Check[1000], B[5];
void static BFS(void) {
int i, j, Now, Dist;
Q.push(0);
Q.push(0);
Check[0]=1;
D[0][0]=0;
while(!Q.empty()) {
Now=Q.front();
Q.pop();
Dist=Q.front();
Q.pop();
if(Now<nh)
D[Now][0]=Dist;
j=A[Now].size();
for(i=0 ; i<j ; i++)
if(!Check[A[Now][i]]) {
Check[A[Now][i]]=1;
Q.push(A[Now][i]);
Q.push(Dist+1);
}
}
}
void static Decoding(int X) {
int i, Temp;
for(i=0 ; i<5 ; i++) {
Temp=X%3;
if(Temp==2)
B[i]=1;
else if(Temp==1)
B[i]=0;
else
B[i]=-1;
X/=3;
}
}
void static DFS(int Now) {
int i, j=A[Now].size(), k;
for(i=0 ; i<j ; i++)
if(!Check[A[Now][i]]) {
Check[A[Now][i]]=1;
for(k=0 ; k<nh ; k++)
D[k][A[Now][i]]+=D[k][Now];
DFS(A[Now][i]);
}
}
void decode(int nv_, int nh_) {
int i, j, k, Temp1, Temp2, X;
nv=nv_;
nh=nh_;
for(i=1 ; i<nv ; i++) {
Temp1=0;
Temp2=1;
for(j=0 ; j<10 ; j++) {
Temp1+=Temp2*decode_bit();
Temp2*=2;
}
A[i].push_back(Temp1);
A[Temp1].push_back(i);
Anc[i]=Temp1;
}
BFS();
X=(nh+4)/5;
for(i=1 ; i<nv ; i++)
for(j=0 ; j<X ; j++) {
Temp1=0;
Temp2=1;
for(k=0 ; k<8 ; k++) {
Temp1+=Temp2*decode_bit();
Temp2*=2;
}
Decoding(Temp1);
for(k=5*j ; k<5*j+5 && k<nh ; k++)
D[k][i]=B[k-5*j];
}
for(i=0 ; i<nv ; i++)
Check[i]=0;
Check[0]=1;
DFS(0);
for(i=0 ; i<nh ; i++)
for(j=0 ; j<nv ; j++)
hops(i,j,D[i][j]);
}
