이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;
static const int N = 1000;
static vector<int> G[N];
static bool vis[N];
static int par[N], dist[N];
void build_tree(int u, int p)
{
vis[u] = true;
par[u] = p;
for (auto v : G[u]) if (v != p && !vis[v])
build_tree(v, u);
}
void bfs(int s)
{
dist[s] = 0;
vis[s] = true;
queue<int> Q;
Q.push(s);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (auto v : G[u]) if (!vis[v]) {
vis[v] = true;
dist[v] = dist[u]+1;
Q.push(v);
}
}
}
void encode_bits(int x, int b)
{
for (int i = 0; i < b; ++i)
encode_bit(((1<<i)&x) ? 1 : 0);
}
static int decis[3];
static int dc = 0;
void encode_delta(int x)
{
decis[dc++] = x+1;
if (dc == 3) {
int v = decis[0]+decis[1]*3+decis[2]*9;
encode_bits(v, 5);
dc = 0;
}
}
void encode(int n, int h, int m, int v1[], int v2[])
{
for (int i = 0; i < m; ++i) {
int u = v1[i], v = v2[i];
G[u].push_back(v);
G[v].push_back(u);
}
build_tree(0, 0);
for (int i = 1; i < n; ++i)
encode_bits(par[i], 10);
for (int i = 0; i < h; ++i) {
fill(vis, vis+n, false);
bfs(i);
for (int j = 1; j < n; ++j)
encode_delta(dist[j]-dist[par[j]]);
}
while (dc != 0)
encode_delta(0);
}
#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;
static const int N = 1000;
static int par[N], chn[N], dp[N];
static bool vis[N];
static vector<int> G[N];
int solve(int u)
{
if (u == 0) return 0;
if (vis[u]) return dp[u];
vis[u] = true;
return dp[u] = chn[u] + solve(par[u]);
}
int decode_bits(int b)
{
int ans = 0;
for (int i = 0; i < b; ++i) {
if (decode_bit())
ans |= (1<<i);
}
return ans;
}
static int decis[3];
static int dc = 0;
int decode_delta()
{
if (dc == 0 || dc == 3) {
dc = 0;
int v = decode_bits(5);
decis[0] = v%3; v /= 3;
decis[1] = v%3; v /= 3;
decis[2] = v;
}
return decis[dc++]-1;
}
void decode(int n, int h)
{
for (int i = 1; i < n; ++i)
par[i] = decode_bits(10);
for (int i = 0; i < h; ++i) {
for (int j = 1; j < n; ++j)
chn[j] = decode_delta();
fill(vis, vis+n, false);
for (int j = 0; j < n; ++j)
hops(i, j, solve(j)-solve(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... |