#include "grader.h"
#include "encoder.h"
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
int const N = 1e3 + 9;
int const H = 36;
vector<int> G[N];
queue<int>Q;
int warstwa[N];
int ojciec[N];
bool odw[N];
int d[N];
void bfs(int v) {
odw[v] = 1;
warstwa[v] = 0;
Q.push(v);
while (!Q.empty()) {
int v = Q.front();
Q.pop();
for (int i = 0; i < G[v].size(); i++) {
int sas = G[v][i];
if (odw[sas] == 0) {
odw[sas] = 1;
warstwa[sas] = warstwa[v] + 1;
Q.push(sas);
}
}
}
}
void dfs(int v, int o) {
odw[v] = 0;
ojciec[v] = o;
d[v] = warstwa[v] - warstwa[o] + 1;
sort(G[v].begin(), G[v].end());
for (int i = 0; i < G[v].size(); i++) {
int sas = G[v][i];
if (odw[sas] == 1) {
dfs(sas, v);
}
}
}
void ll_to_bits(ll a, int b) {
int t = 0;
while (a > 0) {
encode_bit(a % 2);
a /= 2;
t++;
}
while (t < b) {
encode_bit(0);
t++;
}
}
void odll(int nv) {
ll a = 0, mn = 1;
for (int v = 0; v < nv; v++) {
a += mn * d[v];
mn *= 3;
}
ll_to_bits(a, 58);
}
void koduj_drzewo(int nv) {
for (int v = 0; v < nv; v++) {
ll_to_bits(ojciec[v], 10);
}
}
void encode(int nv, int nh, int ne, int* v1, int* v2) {
for (int i = 0; i < ne; i++) {
G[v1[i]].push_back(v2[i]);
G[v2[i]].push_back(v1[i]);
}
bfs(0);
dfs(0, 0);
koduj_drzewo(nv);
ll_to_bits(warstwa[0], 10); //koduj 0
odll(nv);
for (int h = 1; h < nh; h++) {
bfs(h);
dfs(0, 0);
ll_to_bits(warstwa[0], 10); //koduj 0
odll(nv);
}
}
#include "grader.h"
#include "decoder.h"
#include <iostream>
#include <vector>
using namespace std;
typedef long long ll;
int const N = 1e3 + 9;
int O[N];
vector<int> G[N];
int odl[N];
bool ost = true;
bool odw[N];
int d[N];
void policz(int v) {
odw[v] = ost;
d[v] = d[O[v]] + odl[v];
sort(G[v].begin(), G[v].end());
for (int i = 0; i < G[v].size(); i++) {
int syn = G[v][i];
if (odw[syn] != ost) {
policz(syn);
}
}
}
void odzyskaj(int a) {
int t = 0;
while (a > 0) {
odl[t] = (a % 3) - 1;
a /= 3;
t++;
}
while (t < 58) {
odl[t] = -1;
t++;
}
}
void wypisz(int nv, int h) {
for (int v = 0; v < nv; v++) {
hops(h, v, d[v]);
}
}
void fczytaj_ojcuf(int nv) {
for (int v = 0; v < nv; v++) {
int o = 0, mn = 1;
for (int i = 0; i < 10; i++) {
int bit = decode_bit();
o += mn * bit;
mn <<= 1;
}
O[v] = o;
G[o].push_back(v);
}
}
int fczytaj_od_od_zera() {
int o = 0, mn = 1;
for (int i = 0; i < 10; i++) {
int bit = decode_bit();
o += mn * bit;
mn <<= 1;
}
return o;
}
void fczytaj_odl(int nh, int nv) {
for (int h = 0; h < nh; h++) {
d[0] = fczytaj_od_od_zera();
int a = 0, mn = 1;
for (int i = 0; i < 58; i++) {
int bit = decode_bit();
a += mn * bit;
mn <<= 1;
}
odzyskaj(a);
policz(0);
ost = !ost;
wypisz(nv, h);
}
}
void decode(int nv, int nh) {
fczytaj_ojcuf(nv);
fczytaj_odl(nh, nv);
}
Compilation message
encoder.cpp: In function 'void bfs(int)':
encoder.cpp:26:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
26 | for (int i = 0; i < G[v].size(); i++) {
| ~~^~~~~~~~~~~~~
encoder.cpp: In function 'void dfs(int, int)':
encoder.cpp:41:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
41 | sort(G[v].begin(), G[v].end());
| ^~~~
| qsort
encoder.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
42 | for (int i = 0; i < G[v].size(); i++) {
| ~~^~~~~~~~~~~~~
decoder.cpp: In function 'void policz(int)':
decoder.cpp:20:5: error: 'sort' was not declared in this scope; did you mean 'qsort'?
20 | sort(G[v].begin(), G[v].end());
| ^~~~
| qsort
decoder.cpp:21:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
21 | for (int i = 0; i < G[v].size(); i++) {
| ~~^~~~~~~~~~~~~
