Submission #597447

#	Time	Username	Problem	Language	Result	Execution time	Memory
597447		skittles1412	Saveit (IOI10_saveit)	C++17	100 / 100	267 ms	10492 KiB

encoder

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

void encode_bit(int b);

void write(int bits, long x) {
    for (int i = 0; i < bits; i++) {
        encode_bit((x >> i) & 1);
    }
}

void write3(const vector<int>& arr) {
    for (int i = 0; i < sz(arr); i += 29) {
        long cur = 0;
        for (int j = i; j < i + 29; j++) {
            cur *= 3;
            if (j < sz(arr)) {
                cur += arr[j];
            }
        }
        write(46, cur);
    }
}

const int maxn = 1005;

int dist[maxn], par[maxn];
bool vis[maxn];
static vector<int> graph[maxn];

void dfs(int u) {
    vis[u] = true;
    for (auto& v : graph[u]) {
        if (!vis[v]) {
            par[v] = u;
            dfs(v);
        }
    }
}

void encode(int n, int k, int m, int us[], int vs[]) {
    for (int i = 0; i < m; i++) {
        graph[us[i]].push_back(vs[i]);
        graph[vs[i]].push_back(us[i]);
    }
    dfs(0);
    for (int i = 1; i < n; i++) {
        write(10, par[i]);
    }
    auto bfs = [&](int src) -> void {
        memset(dist, -1, sizeof(dist));
        queue<int> q;
        auto push = [&](int u, int d) -> void {
            if (dist[u] == -1) {
                dist[u] = d;
                q.push(u);
            }
        };
        push(src, 0);
        while (sz(q)) {
            int u = q.front();
            q.pop();
            for (auto& v : graph[u]) {
                push(v, dist[u] + 1);
            }
        }
    };
    vector<pair<int, int>> ans;
    vector<int> buf;
    for (int i = 0; i < k; i++) {
        bfs(i);
        for (int j = 1; j < n; j++) {
            buf.push_back(dist[par[j]] - dist[j] + 1);
        }}
    write3(buf);
}

decoder

#include "bits/extc++.h"

using namespace std;

template <typename T>
void dbgh(const T& t) {
    cerr << t << endl;
}

template <typename T, typename... U>
void dbgh(const T& t, const U&... u) {
    cerr << t << " | ";
    dbgh(u...);
}

#ifdef DEBUG
#define dbg(...)                                              \
    cerr << "L" << __LINE__ << " [" << #__VA_ARGS__ << "]: "; \
    dbgh(__VA_ARGS__);
#else
#define dbg(...)
#define cerr   \
    if (false) \
    cerr
#endif

#define endl "\n"
#define long int64_t
#define sz(x) int((x).size())

int decode_bit();
void hops(int h, int c, int d);

long read(int bits) {
    long x = 0;
    for (int i = 0; i < bits; i++) {
        x |= long(decode_bit()) << i;
    }
    return x;
}

int read3() {
    static vector<int> buf;
    if (!sz(buf)) {
        long x = read(46);
        for (int i = 0; i < 29; i++) {
            buf.push_back(x % 3);
            x /= 3;
        }
    }
    int res = buf.back();
    buf.pop_back();
    return res;
}

const int maxn = 1005;

int base;
static vector<pair<int, int>> graph[maxn];

void dfs(int u, int d, int p = -1) {
    hops(base, u, d);
    for (auto& [v, w] : graph[u]) {
        if (v != p) {
            dfs(v, d + w, u);
        }
    }
}

void decode(int n, int k) {
    int par[n];
    for (int i = 1; i < n; i++) {
        par[i] = read(10);
    }
    for (int i = 0; i < k; i++) {
        for (auto& a : graph) {
            a.clear();
        }
        for (int j = 1; j < n; j++) {
            int w = read3() - 1;
            graph[j].emplace_back(par[j], w);
            graph[par[j]].emplace_back(j, -w);
        }
        base = i;
        dfs(i, 0);
    }
}

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