Submission #412428

#	Time	Username	Problem	Language	Result	Execution time	Memory
412428		rainboy	Saveit (IOI10_saveit)	C11	100 / 100	1450 ms	10784 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <stdlib.h>
#include <string.h>

#define N	1000
#define N_	1666

static int *ej[N], eo[N];

void append(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

void bfs(int *dd, int n, int s) {
	static int qu[N];
	int i, head, cnt;

	for (i = 0; i < n; i++)
		dd[i] = n;
	head = cnt = 0;
	dd[s] = 0, qu[head + cnt++] = s;
	while (cnt) {
		int d, o;

		i = qu[cnt--, head++], d = dd[i] + 1;
		for (o = eo[i]; o--; ) {
			int j = ej[i][o];

			if (dd[j] > d)
				dd[j] = d, qu[head + cnt++] = j;
		}
	}
}

static int pp[N]; static char visited[N];

void dfs(int p, int i) {
	int o;

	if (visited[i])
		return;
	visited[i] = 1, pp[i] = p;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		if (j != p)
			dfs(i, j);
	}
}

static int msg[N_];

void mult3() {
	int i;

	for (i = 0; i < N_; i++)
		msg[i] *= 3;
	for (i = 0; i + 1 < N_; i++)
		msg[i + 1] += msg[i] / 2, msg[i] %= 2;
}

void add(int x) {
	int i;

	msg[0] += x;
	for (i = 0; i + 1 < N_; i++)
		msg[i + 1] += msg[i] / 2, msg[i] %= 2;
}

void encode(int n, int k, int m, int *ii, int *jj) {
	static int dd[N];
	int g, h, i, s;

	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (h = 0; h < m; h++)
		append(ii[h], jj[h]), append(jj[h], ii[h]);
	dfs(-1, 0);
	for (i = 1; i < n; i++)
		for (g = 0; g < 10; g++)
			encode_bit(pp[i] >> g & 1);
	for (s = 0; s < k; s++) {
		bfs(dd, n, s);
		memset(msg, 0, N_ * sizeof *msg);
		for (i = n - 1; i > 0; i--)
			mult3(), add(dd[i] - dd[pp[i]] + 1);
		for (i = 0; i < N_; i++)
			encode_bit(msg[i]);
	}
}

decoder

#include "grader.h"
#include "decoder.h"
#include <stdlib.h>
#include <string.h>

#define N	1000
#define N_	1666

static int *ej[N], eo[N];

void append_(int i, int j) {
	int o = eo[i]++;

	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}

static int qu[N], cnt;

void dfs_(int i) {
	int o;

	qu[cnt++] = i;
	for (o = eo[i]; o--; ) {
		int j = ej[i][o];

		dfs_(j);
	}
}

static int msg[N];

void mult2() {
	int i;

	for (i = 0; i < N; i++)
		msg[i] *= 2;
	for (i = 0; i + 1 < N; i++)
		msg[i + 1] += msg[i] / 3, msg[i] %= 3;
}

void add_(int x) {
	int i;

	msg[0] += x;
	for (i = 0; i + 1 < N; i++)
		msg[i + 1] += msg[i] / 3, msg[i] %= 3;
}

void decode(int n, int k) {
	static int pp[N], msg_[N_], dd[N];
	int g, h, i, s;

	for (i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (i = 1; i < n; i++) {
		for (g = 0; g < 10; g++)
			if (decode_bit())
				pp[i] |= 1 << g;
		append_(pp[i], i);
	}
	dfs_(0);
	for (s = 0; s < k; s++) {
		for (i = 0; i < N_; i++)
			msg_[i] = decode_bit();
		memset(msg, 0, N * sizeof *msg);
		for (i = N_ - 1; i >= 0; i--)
			mult2(), add_(msg_[i]);
		for (h = 1; h < n; h++) {
			i = qu[h];
			dd[i] = dd[pp[i]] + msg[i - 1] - 1;
		}
		for (i = 0; i < n; i++)
			hops(s, i, dd[i] - dd[s]);
	}
}

Compilation message (stderr)

encoder.c: In function 'append':
encoder.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

decoder.c: In function 'append_':
decoder.c:14:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   14 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

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