Submission #982629

#	Time	Username	Problem	Language	Result	Execution time	Memory
982629		Sharky	Saveit (IOI10_saveit)	C++17	100 / 100	198 ms	21664 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

namespace Encoder {
    const int inf = 6969;
    int p[1001];
    vector<int> adj[1001], g[1001];
    int dsu[1001], rt[1001];
    bool vis[1001];
    int find(int u) {
        return dsu[u] == u ? u : dsu[u] = find(dsu[u]);
    }
    void merge(int u, int v) {
        dsu[find(v)] = find(u);
    }
    void dfs(int u, int fa, int dist) {
        p[u] = fa;
        // if (u == 1) cout << u << " " << dist << '\n';
        for (int v : adj[u]) if (v != fa) dfs(v, u, dist + 1);
    }
    void dfs2(int u) {
        vis[u] = 1;
        for (int v : g[u]) if (rt[u] + 1 == rt[v] && !vis[v]) {
            adj[u].push_back(v);
            adj[v].push_back(u);
            dfs2(v);
        }
    }
};

using namespace Encoder;

void encode(int n, int h, int m, int *uu, int *vv){
    for (int i = 0; i < n; i++) dsu[i] = i;
    for (int i = 0; i < m; i++) {
        g[uu[i]].push_back(vv[i]);
        g[vv[i]].push_back(uu[i]);
    }
    queue<int> q;
    q.push(0);
    for (int i = 0; i < n; i++) rt[i] = inf;
    rt[0] = 0;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        for (int v : g[u]) if (rt[v] > rt[u] + 1) {
            rt[v] = rt[u] + 1;
            q.push(v);
        }
    }
    // cout << rt[1] << '\n';
    dfs2(0);
    dfs(0, -1, 0);
    // for (int i = 0; i < n; i++) cout << p[i] << ' ';
    // cout << '\n';
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 10; j++) {
            int bit = !!(p[i] & (1 << j));
            encode_bit(bit);
            // cout << "e " << bit << '\n';
        }
    }
    queue<int> bfs;
    vector<int> vt;
    for (int s = 0; s < h; s++) {
        bfs.push(s);
        vector<int> di(n, inf);
        di[s] = 0;
        while (!bfs.empty()) {
            int u = bfs.front();
            bfs.pop();
            for (int v : g[u]) if (di[v] > di[u] + 1) {
                di[v] = di[u] + 1;
                bfs.push(v);
            }
        }
        for (int i = 1; i < n; i++) {
            int delta = di[i] - di[p[i]];
            vt.push_back(delta + 1);
        }
        // if (s == 1) cout << di[0] << ' ' << di[2] << '\n';
    }
    int sz = vt.size();
    while (sz % 3) {
        vt.push_back(0);
        sz++;
    }
    // cout << "encoding\n";
    // for (auto i : vt) cout << i - 1 << ' ';
    // cout << "\n";
    for (int i = 0; i + 2 < sz; i += 3) {
        int x = vt[i] * 9 + vt[i + 1] * 3 + vt[i + 2];
        vector<int> bit;
        while (x) {
            bit.push_back(x % 2);
            x /= 2;
        }
        while ((int) bit.size() < 5) bit.push_back(0);
        reverse(bit.begin(), bit.end());
        for (int e : bit) {
            // cout << "e " << e << '\n';
            encode_bit(e);
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

namespace Decoder {
    int p[1001], d[37], di[1001][1001];
    vector<int> adj[1001], topo;
    void dfs(int u, int fa, int h, int distance) {
        // if (u == 1) cout << u << ' ' << distance << '\n';
        di[u][0] = di[0][u] = distance;
        for (int v : adj[u]) if (v != fa) dfs(v, u, h, distance + 1);
        if (u) topo.push_back(u);
    }
};

using namespace Decoder;

void decode(int n, int h) {
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 10; j++) p[i] += (decode_bit() * (1 << j));
        // cout << p[i] << ' ';
        adj[p[i]].push_back(i);
    }
    // cout << '\n';
    vector<vector<int>> w(h, vector<int> (n, 0));
    dfs(0, -1, h, 0);
    reverse(topo.begin(), topo.end());
    int waves = (h * (n - 1) + 2) / 3;
    // cout << "# bits " << waves * 5 << '\n';
    int hub = 0, city = 1;
    while (waves--) {
        // cout << "hi\n";
        vector<int> bit;
        for (int i = 0; i < 5; i++) bit.push_back(decode_bit());
        int hash = 0;
        for (int i = 0; i < 5; i++) hash = hash * 2 + bit[i];
        vector<int> v(3);
        v[0] = hash / 9;
        hash -= v[0] * 9;
        v[1] = hash / 3;
        hash -= v[1] * 3;
        v[2] = hash;
        for (int i = 0; i < 3; i++) {
            if (hub >= h) break;
            w[hub][city] = v[i] - 1;
            // cout << hub << ' ' << p[city] << ' ' << city << ' ' << v[i] - 1 << '\n';
            city++; if (city == n) city = 1, hub++;
        }
    }
    // cout << "topo\n";
    // for (int j : topo) cout << j << ' ';
    // cout << '\n';
    for (int i = 0; i < h; i++) for (int j : topo) {
        di[i][j] = di[i][p[j]] + w[i][j];
        // if (i == 1 && j == 1) cout << i << ' ' << p[j] << ' ' << di[i][p[j]] << ' ' << w[i][j] << '\n';
    }
    for (int i = 0; i < h; i++) for (int j = 0; j < n; j++) {
        // cout << i << ' ' << j << ' ' << di[i][j] << '\n';
        hops(i, j, di[i][j]);
    }
}

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