This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
void encode(int nv, int nh, int ne, int *v1, int *v2) {
vector<vector<int>> g(nv);
for (int i = 0; i < ne; i++) {
g[v1[i]].push_back(v2[i]);
g[v2[i]].push_back(v1[i]);
}
vector<int> par(nv, -1);
vector<bool> was(nv);
function<void(int, int)> Dfs = [&](int v, int pv) {
par[v] = pv;
was[v] = true;
for (int u : g[v]) {
if (was[u]) {
continue;
}
Dfs(u, v);
}
};
Dfs(0, 0);
for (int v = 0; v < nv; v++) {
for (int b = 0; b < 10; b++) {
encode_bit(par[v] >> b & 1);
}
}
for (int h = 0; h < nh; h++) {
vector<int> dist(nv, -1);
dist[h] = 0;
vector<int> que(1, h);
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j : g[i]) {
if (dist[j] == -1) {
dist[j] = dist[i] + 1;
que.push_back(j);
}
}
}
for (int v = 0; v < nv; v++) {
if (v == h) {
continue;
}
if (v + 2 >= nv) {
if (dist[v] == dist[par[v]]) {
encode_bit(0);
encode_bit(1);
}
if (dist[v] == dist[par[v]] + 1) {
encode_bit(1);
encode_bit(0);
}
if (dist[v] == dist[par[v]] - 1) {
encode_bit(0);
encode_bit(0);
}
continue;
}
int num = 0;
for (int t = v; t < v + 3; t++) {
num = num * 3 + (dist[t] - dist[par[t]] + 1);
}
for (int b = 0; b < 5; b++) {
encode_bit(num >> b & 1);
}
v += 2;
}
}
return;
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
void decode(int nv, int nh) {
vector<int> par(nv);
for (int v = 0; v < nv; v++) {
for (int b = 0; b < 10; b++) {
if (decode_bit()) {
par[v] += (1 << b);
}
}
}
vector<vector<int>> ch(nv);
for (int i = 1; i < nv; i++) {
ch[par[i]].push_back(i);
}
for (int h = 0; h < nh; h++) {
vector<int> d(nv);
for (int v = 0; v < nv; v++) {
if (v == h) {
d[v] = -1;
continue;
}
if (v + 2 >= nv) {
int t = 0;
t += 2 * decode_bit();
t += decode_bit();
d[v] = t - 1;
continue;
}
int num = 0;
for (int b = 0; b < 5; b++) {
if (decode_bit()) {
num += (1 << b);
}
}
for (int t = v + 2; t >= v; t--) {
d[t] = (num % 3) - 1;
num /= 3;
}
v += 2;
}
vector<int> dist(nv, -1);
dist[h] = 0;
vector<int> que(1, h);
for (int b = 0; b < (int) que.size(); b++) {
int i = que[b];
for (int j : ch[i]) {
if (dist[j] == -1) {
dist[j] = dist[i] + d[j];
que.push_back(j);
}
}
if (dist[par[i]] == -1) {
dist[par[i]] = dist[i] - d[i];
que.push_back(par[i]);
}
}
for (int v = 0; v < nv; v++) {
hops(h, v, dist[v]);
}
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |