This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
// M
#include<bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
static const int N = 1009;
static int n, k, m, M[N], P[N], D[N];
static vector < int > Adj[N];
void DFS(int v)
{
M[v] = 1;
for (int u : Adj[v])
if (!M[u])
P[u] = v, DFS(u);
}
void encode(int nv, int nh, int ne, int *v1, int *v2)
{
n = nv; k = nh; m = ne;
for (int i = 0; i < m; i ++)
Adj[v1[i]].push_back(v2[i]), Adj[v2[i]].push_back(v1[i]);
DFS(0);
for (int i = 1; i < n; i ++)
for (int j = 0; j < 10; j ++)
encode_bit((P[i] >> j) & 1);
int C = 5;
int RQB = 8;
for (int h = 0; h < k; h ++)
{
queue < int > qu;
memset(D, -1, sizeof(D));
D[h] = 0; qu.push(h);
while (qu.size())
{
int v = qu.front();
qu.pop();
for (int u : Adj[v])
if (D[u] == -1)
D[u] = D[v] + 1, qu.push(u);
}
for (int i = 0; i < n; i += C)
{
int val = 0;
for (int j = i; j < min(i + C, n); j ++)
{
int r = 0;
if (D[P[j]] == D[j])
r = 1;
if (D[P[j]] > D[j])
r = 2;
val = val * 3 + r;
}
for (int j = 0; j < RQB; j ++)
encode_bit((val >> j) & 1);
}
}
return ;
}
// M
#include<bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
static const int N = 1009;
static int n, k, P[N], D[N], F[N];
static vector < int > Ch[N];
void decode(int nv, int nh)
{
n = nv; k = nh;
for (int i = 1; i < n; i ++)
{
for (int j = 0; j < 10; j ++)
P[i] |= ((int)decode_bit()) << j;
Ch[P[i]].push_back(i);
}
int C = 5;
int RQB = 8;
for (int h = 0; h < k; h ++)
{
for (int i = 0; i < n; i += C)
{
int val = 0;
for (int j = 0; j < RQB; j ++)
val |= ((int)decode_bit()) << j;
for (int j = min(i + C, n) - 1; j >= i; j --)
F[j] = val % 3, val /= 3;
}
memset(D, -1, sizeof(D));
queue < int > qu;
qu.push(h); D[h] = 0;
while (qu.size())
{
int v = qu.front();
qu.pop();
if (v > 0 && D[P[v]] == -1)
{
D[P[v]] = D[v] + F[v] - 1;
qu.push(P[v]);
}
for (int u : Ch[v])
if (D[u] == -1)
{
D[u] = D[v] - F[u] + 1;
qu.push(u);
}
}
for (int i = 0; i < n; i ++)
hops(h, i, D[i]);
}
return ;
}
# | 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... |