Submission #463547

#	Time	Username	Problem	Language	Result	Execution time	Memory
463547		nonsensenonsense1	Saveit (IOI10_saveit)	C++17	100 / 100	347 ms	10308 KiB

encoder

#include "grader.h"
#include <cstring>
#include <vector>
#include <queue>

const int N = 1000;
int pr[N], dist[N];
static std::vector<int> g[N];

static void dfs(int v) 
{
	for (int i = 0; i < (int)g[v].size(); ++i) if (!pr[g[v][i]]) {
		pr[g[v][i]] = v + 1;
		dfs(g[v][i]);
	}
}

void encode(int n, int h, int p, int *a, int *b) 
{
	for (int i = 0; i < p; ++i) {
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	dfs(0);
	for (int i = 1; i < n; ++i) {
		--pr[i];
		for (int j = 0; j < 10; ++j) encode_bit(pr[i] >> j & 1);
	}
	for (int i = 0; i < h; ++i) {
		memset(dist, -1, n << 2);
		std::queue<int> q;
		dist[i] = 0;
		q.push(i);
		while (!q.empty()) {
			int v = q.front();
			q.pop();
			for (int i = 0; i < (int)g[v].size(); ++i) if (dist[g[v][i]] == -1) {
				dist[g[v][i]] = dist[v] + 1;
				q.push(g[v][i]);
			}
		}
		for (int i = 1; i < n; i += 3) {
			int x = 0;
			for (int j = 0; j < 3; ++j) {
				x *= 3;
				if (i + j < n) {
					if (dist[i + j] == dist[pr[i + j]]) ++x;
					else if (dist[i + j] > dist[pr[i + j]]) x += 2;
				}
			}
			for (int j = 0; j < 5; ++j) encode_bit(x >> j & 1);
		}
	}
}

decoder

#include "grader.h"
#include <cstring>
#include <vector>

const int N = 1000;
int p[N], cur, len[N], up[N];
static std::vector<int> g[N];

static void dfs(int v) 
{
	hops(cur, v, len[v] - 1);
	if (v && !len[p[v]]) {
		len[p[v]] = len[v];
		if (!up[v]) ++len[p[v]];
		else if (up[v] == 2) --len[p[v]];
		dfs(p[v]);
	}
	for (int i = 0; i < (int)g[v].size(); ++i) if (!len[g[v][i]]) {
		len[g[v][i]] = len[v];
		if (!up[g[v][i]]) --len[g[v][i]];
		else if (up[g[v][i]] == 2) ++len[g[v][i]];
		dfs(g[v][i]);
	}
}

void decode(int n, int h) 
{
	for (int i = 1; i < n; ++i) {
		for (int j = 0; j < 10; ++j) p[i] |= decode_bit() << j;
		g[p[i]].push_back(i);
	}
	for (int i = 0; i < h; ++i) {
		for (int j = 1; j < n; j += 3) {
			int x = 0;
			for (int k = 0; k < 5; ++k) x |= decode_bit() << k;
			for (int k = 2; k >= 0; --k) {
				if (j + k < n) up[j + k] = x % 3;
				x /= 3;
			}
			x /= 3;
		}
		cur = i;
		memset(len, 0, n << 2);
		len[i] = 1;
		dfs(i);
	}
}

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