oj.uz

Submission #412428

# Submission time Handle Problem Language Result Execution time Memory
412428 2021-05-26T21:18:25 Z rainboy Saveit (IOI10_saveit) C
100 / 100
 1450 ms 10784 KB 
#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]);
	}
}
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 10784 KB Output is correct - 69966 call(s) of encode_bit()
2 Correct 57 ms 4580 KB Output is correct - 5038 call(s) of encode_bit()
3 Correct 1084 ms 5352 KB Output is correct - 68966 call(s) of encode_bit()
4 Correct 91 ms 4576 KB Output is correct - 8370 call(s) of encode_bit()
5 Correct 1087 ms 5564 KB Output is correct - 68966 call(s) of encode_bit()
6 Correct 1142 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
7 Correct 1163 ms 5964 KB Output is correct - 69966 call(s) of encode_bit()
8 Correct 1111 ms 5252 KB Output is correct - 69576 call(s) of encode_bit()
9 Correct 1134 ms 5376 KB Output is correct - 69966 call(s) of encode_bit()
10 Correct 1129 ms 5484 KB Output is correct - 69966 call(s) of encode_bit()
11 Correct 1132 ms 5440 KB Output is correct - 69966 call(s) of encode_bit()
12 Correct 1138 ms 5372 KB Output is correct - 69966 call(s) of encode_bit()
13 Correct 1163 ms 6012 KB Output is correct - 69966 call(s) of encode_bit()
14 Correct 1132 ms 5496 KB Output is correct - 69966 call(s) of encode_bit()
15 Correct 1129 ms 5516 KB Output is correct - 69966 call(s) of encode_bit()
16 Correct 1154 ms 5992 KB Output is correct - 69966 call(s) of encode_bit()
17 Correct 1164 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
18 Correct 1173 ms 6324 KB Output is correct - 69966 call(s) of encode_bit()
19 Correct 1149 ms 6108 KB Output is correct - 69966 call(s) of encode_bit()
20 Correct 1172 ms 6544 KB Output is correct - 69966 call(s) of encode_bit()
21 Correct 1181 ms 6600 KB Output is correct - 69966 call(s) of encode_bit()
22 Correct 1169 ms 6564 KB Output is correct - 69966 call(s) of encode_bit()
23 Correct 1197 ms 6824 KB Output is correct - 69966 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 10784 KB Output is correct - 69966 call(s) of encode_bit()
2 Correct 57 ms 4580 KB Output is correct - 5038 call(s) of encode_bit()
3 Correct 1084 ms 5352 KB Output is correct - 68966 call(s) of encode_bit()
4 Correct 91 ms 4576 KB Output is correct - 8370 call(s) of encode_bit()
5 Correct 1087 ms 5564 KB Output is correct - 68966 call(s) of encode_bit()
6 Correct 1142 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
7 Correct 1163 ms 5964 KB Output is correct - 69966 call(s) of encode_bit()
8 Correct 1111 ms 5252 KB Output is correct - 69576 call(s) of encode_bit()
9 Correct 1134 ms 5376 KB Output is correct - 69966 call(s) of encode_bit()
10 Correct 1129 ms 5484 KB Output is correct - 69966 call(s) of encode_bit()
11 Correct 1132 ms 5440 KB Output is correct - 69966 call(s) of encode_bit()
12 Correct 1138 ms 5372 KB Output is correct - 69966 call(s) of encode_bit()
13 Correct 1163 ms 6012 KB Output is correct - 69966 call(s) of encode_bit()
14 Correct 1132 ms 5496 KB Output is correct - 69966 call(s) of encode_bit()
15 Correct 1129 ms 5516 KB Output is correct - 69966 call(s) of encode_bit()
16 Correct 1154 ms 5992 KB Output is correct - 69966 call(s) of encode_bit()
17 Correct 1164 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
18 Correct 1173 ms 6324 KB Output is correct - 69966 call(s) of encode_bit()
19 Correct 1149 ms 6108 KB Output is correct - 69966 call(s) of encode_bit()
20 Correct 1172 ms 6544 KB Output is correct - 69966 call(s) of encode_bit()
21 Correct 1181 ms 6600 KB Output is correct - 69966 call(s) of encode_bit()
22 Correct 1169 ms 6564 KB Output is correct - 69966 call(s) of encode_bit()
23 Correct 1197 ms 6824 KB Output is correct - 69966 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 10784 KB Output is correct - 69966 call(s) of encode_bit()
2 Correct 57 ms 4580 KB Output is correct - 5038 call(s) of encode_bit()
3 Correct 1084 ms 5352 KB Output is correct - 68966 call(s) of encode_bit()
4 Correct 91 ms 4576 KB Output is correct - 8370 call(s) of encode_bit()
5 Correct 1087 ms 5564 KB Output is correct - 68966 call(s) of encode_bit()
6 Correct 1142 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
7 Correct 1163 ms 5964 KB Output is correct - 69966 call(s) of encode_bit()
8 Correct 1111 ms 5252 KB Output is correct - 69576 call(s) of encode_bit()
9 Correct 1134 ms 5376 KB Output is correct - 69966 call(s) of encode_bit()
10 Correct 1129 ms 5484 KB Output is correct - 69966 call(s) of encode_bit()
11 Correct 1132 ms 5440 KB Output is correct - 69966 call(s) of encode_bit()
12 Correct 1138 ms 5372 KB Output is correct - 69966 call(s) of encode_bit()
13 Correct 1163 ms 6012 KB Output is correct - 69966 call(s) of encode_bit()
14 Correct 1132 ms 5496 KB Output is correct - 69966 call(s) of encode_bit()
15 Correct 1129 ms 5516 KB Output is correct - 69966 call(s) of encode_bit()
16 Correct 1154 ms 5992 KB Output is correct - 69966 call(s) of encode_bit()
17 Correct 1164 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
18 Correct 1173 ms 6324 KB Output is correct - 69966 call(s) of encode_bit()
19 Correct 1149 ms 6108 KB Output is correct - 69966 call(s) of encode_bit()
20 Correct 1172 ms 6544 KB Output is correct - 69966 call(s) of encode_bit()
21 Correct 1181 ms 6600 KB Output is correct - 69966 call(s) of encode_bit()
22 Correct 1169 ms 6564 KB Output is correct - 69966 call(s) of encode_bit()
23 Correct 1197 ms 6824 KB Output is correct - 69966 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 1450 ms 10784 KB Output is correct - 69966 call(s) of encode_bit()
2 Correct 57 ms 4580 KB Output is correct - 5038 call(s) of encode_bit()
3 Correct 1084 ms 5352 KB Output is correct - 68966 call(s) of encode_bit()
4 Correct 91 ms 4576 KB Output is correct - 8370 call(s) of encode_bit()
5 Correct 1087 ms 5564 KB Output is correct - 68966 call(s) of encode_bit()
6 Correct 1142 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
7 Correct 1163 ms 5964 KB Output is correct - 69966 call(s) of encode_bit()
8 Correct 1111 ms 5252 KB Output is correct - 69576 call(s) of encode_bit()
9 Correct 1134 ms 5376 KB Output is correct - 69966 call(s) of encode_bit()
10 Correct 1129 ms 5484 KB Output is correct - 69966 call(s) of encode_bit()
11 Correct 1132 ms 5440 KB Output is correct - 69966 call(s) of encode_bit()
12 Correct 1138 ms 5372 KB Output is correct - 69966 call(s) of encode_bit()
13 Correct 1163 ms 6012 KB Output is correct - 69966 call(s) of encode_bit()
14 Correct 1132 ms 5496 KB Output is correct - 69966 call(s) of encode_bit()
15 Correct 1129 ms 5516 KB Output is correct - 69966 call(s) of encode_bit()
16 Correct 1154 ms 5992 KB Output is correct - 69966 call(s) of encode_bit()
17 Correct 1164 ms 5792 KB Output is correct - 69966 call(s) of encode_bit()
18 Correct 1173 ms 6324 KB Output is correct - 69966 call(s) of encode_bit()
19 Correct 1149 ms 6108 KB Output is correct - 69966 call(s) of encode_bit()
20 Correct 1172 ms 6544 KB Output is correct - 69966 call(s) of encode_bit()
21 Correct 1181 ms 6600 KB Output is correct - 69966 call(s) of encode_bit()
22 Correct 1169 ms 6564 KB Output is correct - 69966 call(s) of encode_bit()
23 Correct 1197 ms 6824 KB Output is correct - 69966 call(s) of encode_bit()