Submission #60481

#	Time	Username	Problem	Language	Result	Execution time	Memory
60481		aquablitz11	Saveit (IOI10_saveit)	C++14	100 / 100	292 ms	11592 KiB

encoder

#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);
}

decoder

#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));
    }
}

• Subtask 1: 25 / 25
• Subtask 2: 25 / 25
• Subtask 3: 25 / 25
• Subtask 4: 25 / 25