#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
void encode(int n, int h, int p, int a[], int b[]){
vector<int>adj[1001];
int dis[1001],par[1001];
for(int i = 0; i < n; i++) {
dis[i] = INT_MAX;
}
for(int i = 0; i < p; i++){
adj[a[i]].push_back(b[i]);
adj[b[i]].push_back(a[i]);
}
dis[0] = par[0] = 0;
vector<int>d = {0};
int j = 0;
while(j < d.size()){
for(auto s: adj[d[j]]){
if(dis[s] == INT_MAX){
dis[s] = dis[d[j]] + 1;
par[s] = d[j];
d.push_back(s);
}
}
j++;
}
for(int i = 1; i < n; i++){
for(int k = 0; k < 10; k++){
if(par[i] & (1 << k)) encode_bit(1);
else encode_bit(0);
}
}
for(int i = 1; i < h; i++){
vector<int>pc(n, INT_MAX);
pc[i] = 0;
int j = 0;
vector<int>b = {i};
while(j < b.size()){
for(auto s:adj[b[j]]){
if(pc[s] == INT_MAX){
pc[s] = pc[b[j]] + 1;
b.push_back(s);
}
}
j++;
}
for(int k = 1; k < n; k++){
int diff = pc[k] - pc[par[k]];
if(diff != 0){
encode_bit(1);
if(diff < 0) encode_bit(1);
else encode_bit(0);
}else{
encode_bit(0);
}
}
}
}
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
void reset(int n){
j = 0;
for(int i = 0; i < n; i++) {
adj[i].clear();
dis[i] = INT_MAX;
}
for(int i = 0; i < n; i++){
for(int k = 0; k < n; k++) diff[i][k] = 0;
}
}
void decode(int n, int h){
vector<int>adj[1001];
int dis[1001],p[1001],diff[1001][1001],j;
j = 0;
for(int i = 0; i < n; i++) {
dis[i] = INT_MAX;
}
for(int i = 0; i < n; i++){
for(int k = 0; k < n; k++) diff[i][k] = 0;
}
for(int i = 1; i < n; i++){
int parent = 0;
for(int k = 0; k < 10; k++){
if(decode_bit()) parent += (1 << k);
}
p[i] = parent;
adj[i].push_back(parent);
adj[parent].push_back(i);
}
dis[0] = j = 0;
vector<int>b = {0};
while(j < b.size()){
for(auto s: adj[b[j]]){
if(dis[s] == INT_MAX){
dis[s] = dis[b[j]] + 1;
}
}
j++;
}
for(int i = 0; i < n; i++) hops(0,i, dis[i]);
for(int i = 1; i < h; i++){
for(int k = 1; k < n; k++){
if(!decode_bit()){
diff[k][p[k]] = diff[p[k]][k] = 0;
}else{
if(decode_bit()){
diff[k][p[k]] = -1;
diff[p[k]][k] = 1;
}else{
diff[p[k]][k] = -1;
diff[k][p[k]] = 1;
}
}
}
vector<int>pc(n, INT_MAX);
pc[i] = j = 0;
vector<int>bb = {i};
while(j < bb.size()){
for(auto s:adj[bb[j]]){
if(pc[s] == INT_MAX){
pc[s] = pc[bb[j]] + diff[bb[j]][s];
bb.push_back(s);
}
}
j++;
}
for(int t = 0; t < n; t++){
hops(i,t,pc[t]);
}
}
}
Compilation message
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:26:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | while(j < d.size()){
| ~~^~~~~~~~~~
encoder.cpp:48:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
48 | while(j < b.size()){
| ~~^~~~~~~~~~
decoder.cpp: In function 'void reset(int)':
decoder.cpp:9:5: error: 'j' was not declared in this scope
9 | j = 0;
| ^
decoder.cpp:11:9: error: 'adj' was not declared in this scope
11 | adj[i].clear();
| ^~~
decoder.cpp:12:9: error: 'dis' was not declared in this scope; did you mean 'div'?
12 | dis[i] = INT_MAX;
| ^~~
| div
decoder.cpp:15:36: error: 'diff' was not declared in this scope
15 | for(int k = 0; k < n; k++) diff[i][k] = 0;
| ^~~~
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:42:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | while(j < b.size()){
| ~~^~~~~~~~~~
decoder.cpp:70:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
70 | while(j < bb.size()){
| ~~^~~~~~~~~~~
