Submission #29164

#	Time	Username	Problem	Language	Result	Execution time	Memory
29164		Nirjhor	Saveit (IOI10_saveit)	C++14	100 / 100	423 ms	11896 KiB

encoder

#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

const int H = 40;
const int N = 1010;

static vector <int> g[N];
static vector <int> t[N];
static int n, h, d[H][N];
static int p[N], a[H * N];
static int par[N];

void send (int x, int bit) {
	for (int i = 0; i < bit; ++i) {
		encode_bit(x & 1);
		x >>= 1;
	}
}

void go (int u, int from) {
	p[u] = from;
	for (int it = 0; it < int(g[u].size()); ++it) {
		int v = g[u][it];
		if (p[v] != -1) continue;
		go(v, u);
	}
}

void dfs (int u, int from = -123) {
	par[u] = from;
	for (int it = 0; it < int(t[u].size()); ++it) {
		int v = t[u][it];
		if (par[v] != -1) continue;
		dfs(v, u);
	}
}

void bfs (int root) {
	queue <int> q;
	d[root][root] = 0;
	q.push(root);
	while (not q.empty()) {
		int u = q.front();
		q.pop();
		for (int it = 0; it < int(g[u].size()); ++it) {
			int v = g[u][it];
			if (d[root][v] != -1) continue;
			d[root][v] = d[root][u] + 1;
			q.push(v);
		}
	}
}

void encode (int _n, int _h, int _p, int a[], int b[]) {
	n = _n, h = _h;
	for (int i = 0; i < _p; ++i) {
		g[a[i]].push_back(b[i]);
		g[b[i]].push_back(a[i]);
	}
	memset(p, -1, sizeof p);
	memset(d, -1, sizeof d);
	go(0, 0);
	for (int i = 1; i < n; ++i) {
		send(p[i], 10);
		t[i].push_back(p[i]);
		t[p[i]].push_back(i);
	}
	int ptr = 0;
	for (int i = 0; i < h; ++i) {
		memset(par, -1, sizeof par);
		bfs(i), dfs(i);
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			int diff = d[i][j] - d[i][par[j]];
			assert(abs(diff) <= 1);
			a[ptr++] = diff + 1;
		}
	}
	if (ptr % 3) ptr += 3, ptr -= (ptr % 3);
	for (int i = 0; i < ptr; i += 3) {
		int x = 0;
		for (int j = i; j < i + 3; ++j) {
			x *= 3, x += a[j];
		}
		send(x, 5);
	}
}

decoder

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using namespace std;

const int H = 40;
const int N = 1010;

static vector <int> g[N];
static int n, h, p[N];
static int a[H * N], b[H][N];

int receive (int bit) {
	int x = 0;
	for (int i = 0; i < bit; ++i) {
		if (decode_bit()) {
			x |= 1 << i;
		}
	}
	return x;
}

void travel (int u, int from = -123) {
	p[u] = from;
	for (int it = 0; it < int(g[u].size()); ++it) {
		int v = g[u][it];
		if (v == from) continue;
		travel(v, u);
	}
}

int find (int u, int v) {
	if (u == v) return 0;
	int ret = find(u, p[v]);
	ret += b[u][v];
	return ret;
}

void decode (int _n, int _h) {
	n = _n, h = _h;
	for (int i = 1; i < n; ++i) {
		int j = receive(10);
		g[j].push_back(i);
		g[i].push_back(j);
	}
	int ptr = h * n - h;
	if (ptr % 3) ptr += 3, ptr -= (ptr % 3);
	for (int i = 0; i < ptr; i += 3) {
		int x = receive(5);
		for (int j = i + 2; j >= i; --j) {
			a[j] = x % 3, x /= 3;
		}
	}
	ptr = 0;
	for (int i = 0; i < h; ++i) {
		for (int j = 0; j < n; ++j) {
			if (i == j) continue;
			b[i][j] = a[ptr++] - 1;
		}
	}
	for (int i = 0; i < h; ++i) {
		memset(p, -1, sizeof p);
		travel(i);
		for (int j = 0; j < n; ++j) {
			hops(i, j, find(i, j));	
		}
	}
}

Compilation message (stderr)

encoder.cpp:13:18: warning: 'a' defined but not used [-Wunused-variable]
 static int p[N], a[H * N];
                  ^

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