Submission #461035

#	Time	Username	Problem	Language	Result	Execution time	Memory
461035		nonsensenonsense1	Saveit (IOI10_saveit)	C++17	50 / 100	315 ms	12416 KiB

encoder

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

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

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]);
	}
	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 = 0; i < n; ++i) for (int j = 0; j < 10; ++j) encode_bit(dist[i] >> j & 1);
	}
}

decoder

#include "grader.h"

void decode(int n, int h) 
{
	for (int i = 0; i < h; ++i) for (int j = 0; j < n; ++j) {
		int d = 0;
		for (int k = 0; k < 10; ++k) d |= decode_bit() << k;
		hops(i, j, d);
	}
}

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