#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
vector<int> v[1002];
int dist[40][1002], tt[40][1002], state[1002];
void encode(int n, int h, int m, int *a, int *b)
{
for(int i = 0; i < m; ++i)
{
v[a[i]].push_back(b[i]);
v[b[i]].push_back(a[i]);
}
for(int i = 0; i < h; ++i)
{
for(int j = 0; j < n; ++j)
dist[i][j] = (1<<30);
dist[i][i] = 0;
deque<int> d;
while(!d.empty())
{
int nod = d[0];
d.pop_front();
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(dist[i][vecin] > dist[i][nod] + 1)
{
dist[i][vecin] = dist[i][nod] + 1;
tt[i][vecin] = nod;
d.push_back(vecin);
}
}
}
if(i == 0)
for(int j = 1; j < n; ++j)
for(int x = 0; x < 10; ++x)
encode_bit((tt[0][j] & (1<<x)) != 0);
for(int j = 0; j < n; ++j)
{
if(dist[i][j] == dist[i][tt[0][j]])
state[j] = 0;
else
if(dist[i][j] > dist[i][tt[0][j]])
state[j] = 1;
else
state[j] = 2;
}
// 5 states with 8 bits
for(int j = 0; j < n; j += 5)
{
int msk = 0;
for(int x = j; x < min(n-1, j + 4); ++x)
msk = msk * 3 + state[x];
for(int pw = 0; pw <= 7; ++pw)
encode_bit((msk & (1<<pw)) != 0);
}
}
}
#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
vector<int> v[1002];
int tt[1002], dist[40][1002], state[1002];
void dfs(int h, int dad, int nod)
{
dist[h][nod] = dist[h][tt[nod]] + (s[nod] + 1) % 3 - 1;
for(int i = 0; i < v[nod].size(); ++i)
{
int vecin = v[nod][i];
if(vecin == dad)
continue;
dfs(h, nod, vecin);
}
}
void decode(int n, int h)
{
for(int i = 1; i < n; ++i)
{
int wh = 0;
for(int j = 0; j <= 9; ++j)
wh = wh + (1<<j) * decode_bit();
tt[i] = wh;
v[wh].push_back(i);
}
for(int i = 0; i < h; ++i)
{
for(int j = 0; j < n; j += 5)
{
int val = 0;
for(int xx = 0; xx <= 7; ++xx)
val = val * 3 + decode_bit();
for(int xx = min(n - 1, j + 4); xx >= j; --xx)
{
state[xx] = val % 3;
val /= 3;
}
}
int nd = i;
while(nd != tt[nd])
{
dist[i][tt[nd]] = dist[i][nd] - (state[nd] + 1) % 3 + 1;
nd = tt[nd];
}
dfs(i, -1, 0);
for(int j = 0; j < n; ++j)
hops(i, j, dist[i][j]);
}
}
Compilation message
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:27:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
decoder.cpp: In function 'void dfs(int, int, int)':
decoder.cpp:13:40: error: 's' was not declared in this scope
dist[h][nod] = dist[h][tt[nod]] + (s[nod] + 1) % 3 - 1;
^
decoder.cpp:14:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < v[nod].size(); ++i)
~~^~~~~~~~~~~~~~~
