| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1338784 | QuocSensei | Saveit (IOI10_saveit) | C++20 | 0 ms | 0 KiB |
#include "encoder.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << endl
#define BIT(n) ((1ll) << (n))
#define bit(mask, i) (((mask) >> (i)) & 1)
using namespace std;
namespace ENCODER
{
const int maxn = 1e3;
const int maxh = 36;
const int maxlog = __lg(maxn * maxh);
int dist[maxh + 10][maxn + 10], n, h;
vector<int> adj[maxn + 10];
void bfs(int source)
{
for (int i = 0; i < n; i++)
dist[source][i] = -1;
queue<int> q;
dist[source][source] = 0;
q.push(source);
while (q.size())
{
int top = q.front();
q.pop();
for (int next_top : adj[top])
{
if (dist[source][next_top] != -1)
continue;
dist[source][next_top] = dist[source][top] + 1;
q.push(next_top);
}
}
}
void encode(int _N, int _H, int P, int A[], int B[])
{
n = _N;
h = _H;
for (int i = 0; i < P; i++)
{
adj[A[i]].push_back(B[i]);
adj[B[i]].push_back(A[i]);
}
for (int i = 0; i < h; i++)
{
bfs(i);
for (int j = 0; j < n; j++)
{
for (int k = maxlog; k >= 0; k--)
encode_bit(bit(dist[i][j], k));
}
}
}
}
void encode(int _N, int _H, int P, int A[], int B[])
{
ENCODER::encode(_N, _H, P, A, B);
}#include "decoder.h"
#include <bits/stdc++.h>
#define ll long long
#define el cout << endl
#define BIT(n) ((1ll) << (n))
#define bit(mask, i) (((mask) >> (i)) & 1)
using namespace std;
namespace DECODER
{
const int maxn = 1e3;
const int maxh = 36;
const int maxlog = __lg(maxh * maxn);
int n, h;
void decode(int _N, int _H)
{
n = _N;
h = _H;
for (int i = 0; i < h; i++)
for (int j = 0; j < n; j++)
{
int dist = 0;
for (int k = maxlog; k >= 0; k--)
dist += BIT(k) * decode_bit();
hops(i, j, dist);
}
}
}
void decode(int _N, int _H)
{
DECODER::decode(_N, _H);
}