Submission #201471

#	Time	Username	Problem	Language	Result	Execution time	Memory
201471		dolphingarlic	Saveit (IOI10_saveit)	C++14	100 / 100	264 ms	12272 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;

vector<int> graph[1000];
int par[1000], dist[1000][36], state[1000];
bool visited[1000];

void dfs(int node = 0, int parent = 0) {
    par[node] = parent;
    visited[node] = true;
    for (int i : graph[node]) if (!visited[i]) dfs(i, node);
}

void encode(int nv, int nh, int ne, int *v1, int *v2) {
    FOR(i, 0, ne) {
        graph[v1[i]].push_back(v2[i]);
        graph[v2[i]].push_back(v1[i]);
    }
    dfs();
    FOR(i, 0, nv) FOR(j, 0, 10) encode_bit((par[i] & (1 << j)) >> j);

    FOR(hub, 0, nh) {
        dist[hub][hub] = 1;
        queue<int> q;
        q.push(hub);
        while (q.size()) {
            int curr = q.front();
            q.pop();
            for (int i : graph[curr]) if (!dist[i][hub]) {
                dist[i][hub] = dist[curr][hub] + 1;
                q.push(i);
            }
        }

        FOR(i, 0, nv) {
            if (dist[i][hub] == dist[par[i]][hub]) state[i] = 0;
            else if (dist[i][hub] > dist[par[i]][hub]) state[i] = 1;
            else state[i] = 2;
        }
        for (int i = 0; i < nv; i += 5) {
            int enc = 0;
            FOR(j, i, min(i + 5, nv)) enc = (enc * 3 + state[j]);
            FOR(j, 0, 8) encode_bit((enc & (1 << j)) >> j);
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

vector<int> graph[1000];
int par[1000], dist[1000][36], state[1000];

void dfs(int hub, int node = 0, int parent = 0) {
    dist[node][hub] = dist[par[node]][hub] + (state[node] + 1) % 3 - 1;
    for (int i : graph[node]) if (i != parent) dfs(hub, i, node);
}

void decode(int nv, int nh) {
    FOR(i, 0, nv) {
        FOR(j, 0, 10) par[i] += decode_bit() << j;
        graph[par[i]].push_back(i);
    }

    FOR(hub, 0, nh) {
        for (int i = 0; i < nv; i += 5) {
            int enc = 0;
            FOR(j, 0, 8) enc += decode_bit() << j;
            for (int j = min(i + 5, nv) - 1; j >= i; j--) {
                state[j] = enc % 3;
                enc /= 3;
            }
        }

        int curr = hub;
        while (curr != par[curr]) {
            dist[par[curr]][hub] = dist[curr][hub] - (state[curr] + 1) % 3 + 1;
            curr = par[curr];
        }
        dfs(hub);

        FOR(i, 0, nv) hops(hub, i, dist[i][hub]);
    }
}

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