oj.uz

Submission #29164

# Submission time Handle Problem Language Result Execution time Memory
29164 2017-07-18T12:55:31 Z Nirjhor Saveit (IOI10_saveit) C++14
100 / 100
 423 ms 11896 KB 
#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);
	}
}


#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

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

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 11896 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 71 ms 6200 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 7 ms 4872 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 94 ms 6280 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 99 ms 6348 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 144 ms 6572 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 73 ms 6188 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 55 ms 6060 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 50 ms 6148 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 53 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 81 ms 6268 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 139 ms 6764 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 87 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 89 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 174 ms 6724 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 6504 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 118 ms 6916 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 101 ms 6576 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 153 ms 7152 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 137 ms 7236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 106 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 151 ms 7420 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 11896 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 71 ms 6200 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 7 ms 4872 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 94 ms 6280 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 99 ms 6348 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 144 ms 6572 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 73 ms 6188 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 55 ms 6060 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 50 ms 6148 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 53 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 81 ms 6268 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 139 ms 6764 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 87 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 89 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 174 ms 6724 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 6504 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 118 ms 6916 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 101 ms 6576 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 153 ms 7152 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 137 ms 7236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 106 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 151 ms 7420 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 11896 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 71 ms 6200 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 7 ms 4872 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 94 ms 6280 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 99 ms 6348 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 144 ms 6572 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 73 ms 6188 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 55 ms 6060 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 50 ms 6148 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 53 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 81 ms 6268 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 139 ms 6764 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 87 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 89 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 174 ms 6724 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 6504 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 118 ms 6916 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 101 ms 6576 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 153 ms 7152 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 137 ms 7236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 106 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 151 ms 7420 KB Output is correct - 69930 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 423 ms 11896 KB Output is correct - 69930 call(s) of encode_bit()
2 Correct 7 ms 4796 KB Output is correct - 60 call(s) of encode_bit()
3 Correct 71 ms 6200 KB Output is correct - 62930 call(s) of encode_bit()
4 Correct 7 ms 4872 KB Output is correct - 75 call(s) of encode_bit()
5 Correct 94 ms 6280 KB Output is correct - 62930 call(s) of encode_bit()
6 Correct 99 ms 6348 KB Output is correct - 69930 call(s) of encode_bit()
7 Correct 144 ms 6572 KB Output is correct - 69930 call(s) of encode_bit()
8 Correct 73 ms 6188 KB Output is correct - 67200 call(s) of encode_bit()
9 Correct 55 ms 6060 KB Output is correct - 69930 call(s) of encode_bit()
10 Correct 50 ms 6148 KB Output is correct - 69930 call(s) of encode_bit()
11 Correct 53 ms 6216 KB Output is correct - 69930 call(s) of encode_bit()
12 Correct 81 ms 6268 KB Output is correct - 69930 call(s) of encode_bit()
13 Correct 139 ms 6764 KB Output is correct - 69930 call(s) of encode_bit()
14 Correct 87 ms 6204 KB Output is correct - 69930 call(s) of encode_bit()
15 Correct 89 ms 6232 KB Output is correct - 69930 call(s) of encode_bit()
16 Correct 174 ms 6724 KB Output is correct - 69930 call(s) of encode_bit()
17 Correct 117 ms 6504 KB Output is correct - 69930 call(s) of encode_bit()
18 Correct 118 ms 6916 KB Output is correct - 69930 call(s) of encode_bit()
19 Correct 101 ms 6576 KB Output is correct - 69930 call(s) of encode_bit()
20 Correct 153 ms 7152 KB Output is correct - 69930 call(s) of encode_bit()
21 Correct 137 ms 7236 KB Output is correct - 69930 call(s) of encode_bit()
22 Correct 106 ms 6820 KB Output is correct - 69930 call(s) of encode_bit()
23 Correct 151 ms 7420 KB Output is correct - 69930 call(s) of encode_bit()