Submission #63905

#	Time	Username	Problem	Language	Result	Execution time	Memory
63905		YaDon4ick	Saveit (IOI10_saveit)	C++14	100 / 100	249 ms	11560 KiB

encoder

#include "grader.h"
#include "encoder.h"

//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = 1005;
const int K = 40;

using namespace std;

static int n, d[K][N], parent[N];
static vector < int > g[N];

void bfs(int start)
{
	fill(d[start], d[start] + n, -1);
	d[start][start] = 0;
	queue < int > q;
	q.push(start);
	while(!q.empty())
	{
		int v = q.front();
		q.pop();
		for (auto to : g[v])
		{
			if (d[start][to] == -1)
			{
				d[start][to] = d[start][v] + 1;
				q.push(to);
			}
		}
	}
}

void dfs(int v)
{
	for (auto to : g[v])
	{
		if (parent[to] == -1)
		{
			parent[to] = v;
			dfs(to);
		}	
	}
}

void encodeNum(int x, int len)
{
	for (int i = 0; i < len; i++)
	{
		encode_bit(x & 1);
		x >>= 1;
	}
}

void encode(int _n, int k, int m, int *v1, int *v2)
{
	n = _n;	
	//~read
	for (int i = 0; i < m; i++)
	{
		int v = v1[i], u = v2[i];
		g[v].pb(u), g[u].pb(v);
	}
	//~calc_d
	for (int i = 0; i < k; i++)
		bfs(i);
	//~spanning_tree
	fill(parent, parent + n, -1);
	dfs(0);	
	//~encode_tree
	for (int i = 1; i < n; i++)
		encodeNum(parent[i], 10);
  	//~encode_dist_from_0
  	for (int i = 0; i < k; i++)
  		encodeNum(d[0][i], 10);
	//~encode_res
	for (int v = 0; v < k; v++)
	{	
		for (int j = 0; j < n; j += 5)
		{
			int mask = 0;
			for (int u = min(n - 1, j + 4); u >= j; u--)
			{
				mask *= 3;
				if (d[v][u] == d[v][parent[u]])
					mask++;
				else if (d[v][u] == d[v][parent[u]] + 1)
					mask += 2;				
			}
			encodeNum(mask, 8);
		}	
	}
  	return;
}

decoder

#include "grader.h"
#include "decoder.h"

//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = 1005;
const int K = 40;

using namespace std;

vector < int > g[N];
int d[K][N], add[K][N];

int decodeNum(int len)
{
	int res = 0;
	for (int i = 0; i < len; i++)
	{
		int bit = decode_bit();
		res += bit * (1 << i);		
	}
	return res;	
}

void decode(int n, int k) 
{
	//~decode_tree
	for (int v = 1; v < n; v++)
	{
		int u = decodeNum(10);
		g[u].pb(v);
	}
	//~decode_d
	for (int i = 0; i < k; i++)
		d[i][0] = decodeNum(10);
	//~decode_add
	for (int i = 0; i < k; i++)
	{
		for (int j = 0; j < n; j += 5)
		{
			int mask = decodeNum(8);
			for (int u = j; u < j + 5 && u < n; u++)
			{
				add[i][u] = (mask % 3) - 1;
				mask /= 3;
			}			
		}                           	
	}
	//~solve
	for (int i = 0; i < k; i++)
	{
		queue < int > q;
		q.push(0);
		while(!q.empty())
		{
			int v = q.front();
			q.pop();
			for (auto to : g[v])
			{
				d[i][to] = d[i][v] + add[i][to];
				q.push(to);
			}
		}
	}
	//~decode_ans
	for (int i = 0; i < k; i++)
		for (int j = 0; j < n; j++)
			hops(i, j, d[i][j]);
}

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