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;
typedef pair<int,int> pii;
const int INF = 1e9;
static vector<int> g[1000];
static vector<pii> tr[1000];
static int dst[1000], vals[1000], seen[1000], par[1000];
template <int n>
void encode_num(int x) {
bitset<n> bits(x);
for (int i = 0; i < n; ++i) encode_bit(bits[i]);
}
void dfs_tr(int u) {
seen[u] = 1;
for (int v: g[u]) if (!seen[v]) {
par[v] = u;
tr[u].push_back({v, v});
tr[v].push_back({u, v});
dfs_tr(v);
}
}
void dfs(int u, int p) {
for (pii e: tr[u]) if (e.first != p) {
vals[e.second] = dst[e.first] - dst[u] + 1;
dfs(e.first, u);
}
}
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]);
}
dfs_tr(0);
for (int i = 1; i < nv; ++i) encode_num<10>(par[i]);
for (int i = 0; i < nh; ++i) {
queue<int> bfs;
fill(dst, end(dst), INF);
bfs.push(i);
dst[i] = 0;
while (bfs.size()) {
int u = bfs.front(); bfs.pop();
for (int v: g[u]) {
if (dst[u]+1 < dst[v]) {
dst[v] = dst[u]+1;
bfs.push(v);
}
}
}
dfs(i, -1);
for (int j = 0; j < 1000; j += 5) {
int v = 0;
for (int k = 0; k < 5; ++k) {
v*=3;
v+=vals[j+k];
}
encode_num<8>(v);
}
/*for (int k = 0; k < nv; ++k) cerr << dst[k] << ' ';
cerr << '\n';*/
}
}
#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
static vector<pii> tr[1000];
static int vals[1000];
void dfs(int u, int p, int d, int h) {
hops(h, u, d);
// cerr << h << ' ' << u << ' ' << d << endl;
for (pii e: tr[u]) if (e.first != p) {
dfs(e.first, u, d + vals[e.second], h);
}
}
template <int n>
int decode_num() {
bitset<n> bits;
for (int i = 0; i < n; ++i) bits[i] = decode_bit();
return bits.to_ulong();
}
void decode(int nv, int nh) {
for (int i = 1; i < nv; ++i) {
int p = decode_num<10>();
tr[p].push_back({i,i});
tr[i].push_back({p,i});
}
for (int i = 0; i < nh; ++i) {
for (int j = 0; j < 200; j++) {
int v = decode_num<8>();
for (int k = 0; k < 5; ++k) {
vals[j*5+4-k] = (v%3)-1;
v/=3;
}
}
dfs(i, -1, 0, i);
}
}
# | 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... |