Submission #201940

#	Time	Username	Problem	Language	Result	Execution time	Memory
201940		luciocf	Saveit (IOI10_saveit)	C++14	50 / 100	291 ms	14224 KiB

encoder

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

using namespace std;

const int maxn = 1e3+10;

static int dist[maxn][maxn];

static bool mark[maxn];

static vector<int> grafo[maxn];

void bfs(int x)
{
	queue<int> fila;

	fila.push(x), mark[x] = 1;

	while (!fila.empty())
	{
		int u = fila.front(); fila.pop();

		for (auto v: grafo[u])
		{
			if (!mark[v])
			{
				dist[x][v] = dist[x][u]+1, mark[v] = 1;
				fila.push(v);
			}
		}
	}
}

void encode(int n, int h, int m, int *a, int *b)
{
	for (int i = 1; i <= m; i++)
	{
		a[i-1]++, b[i-1]++;

		grafo[a[i-1]].push_back(b[i-1]);
		grafo[b[i-1]].push_back(a[i-1]);
	}

	for (int i = 1; i <= h; i++)
	{
		memset(mark, 0, sizeof mark);

		bfs(i);
	}

	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			for (int b = 0; b < 10; b++)
				encode_bit((dist[i][j]&(1<<b)) > 0);
		}
	}
}

decoder

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

using namespace std;

void decode(int n, int h)
{
	for (int i = 1; i <= h; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			int d = 0;

			for (int b = 0; b < 10; b++)
				d += decode_bit()*(1<<b);

			hops(i-1, j-1, d);
		}
	}
}

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