Submission #220834

#	Time	Username	Problem	Language	Result	Execution time	Memory
220834		Lawliet	Saveit (IOI10_saveit)	C++17	0 / 100	246 ms	12272 KiB

encoder

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

using namespace std;
typedef long long int lli;

const int MAXH = 40;
const int MAXN = 1010;

int dad[MAXN][MAXH];
int dist[MAXN][MAXH];

bool marc[MAXN][MAXH];

vector< int > adj[MAXN];

queue< int > q;

bool isActive(lli mask, int k) { return mask & (1LL << k); }

void print(lli val, int b)
{
	for(int i = 0 ; i < b ; i++)
	{
		if( isActive( val , i ) ) encode_bit( 1 );
		else encode_bit( 0 );
	}
}

void add(int cur, int d, int p, int ind)
{
	q.push( cur );

	dad[cur][ind] = p;
	dist[cur][ind] = d;
	marc[cur][ind] = true;
}

void BFS(int source, int ind, bool needPrint = false)
{
	add( source , 0 , source , ind );

	while( !q.empty() )
	{
		int cur = q.front();
		q.pop();

		if( needPrint && cur != 0 )
			print( dad[cur][0] , 10 );

		for(int i = 0 ; i < adj[cur].size() ; i++)
		{
			int viz = adj[cur][i];

			if( marc[viz][ind] ) continue;

			add( viz , dist[cur][ind] + 1 , cur , ind );
		}
	}
}

void encode(int N, int H, int E, int *U, int *V)
{
	for(int i = 0 ; i < E ; i++)
	{
		adj[ U[i] ].push_back( V[i] );
		adj[ V[i] ].push_back( U[i] );
	}

	BFS( 0 , 0 , true );

	for(int j = 1 ; j < H ; j++)
	{
		BFS( j , j );
		print( dist[0][j] , 10 );
	}

	for(int i = 1 ; i < N ; i++)
	{
		int U = i;
		int V = dad[i][0];

		lli sum = 0;

		for(int j = 1 ; j < H ; j++)
		{
			lli v;
			if( dist[U][j] < dist[V][j] ) v = 0;
			if( dist[U][j] == dist[V][j] ) v = 1;
			if( dist[U][j] > dist[V][j] ) v = 2;

			sum = 3*sum + v;
		}

		print( sum , 56 );
	}
}

decoder

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

using namespace std;
typedef long long int lli;
typedef pair<int,int> pii;

const int MAXH = 40;
const int MAXN = 1010;

int dist[MAXN][MAXH];

vector< int > adj[MAXN];
vector< int > digits[MAXN];

lli read(int b)
{
	lli val = 0;

	for(int i = 0 ; i < b ; i++)
	{
		int curBit = decode_bit();
		if( curBit == 1 ) val += (1LL << i);
	}

	return val;
}

void toTernaryBase(lli val, int edge, int H)
{
	lli curPot = 1;

	for(int i = 0 ; i < H - 2 ; i++)
		curPot *= 3;

	for(int i = 0 ; i < H - 1 ; i++, curPot /= 3)
	{
		for(int j = 1 ; j <= 3 ; j++)
		{
			if( val < j*curPot )
			{
				digits[edge].push_back( j - 1 );
				val -= (j - 1)*curPot;

				break;
			}
		}
	}
}

void DFS(int cur, int H)
{
	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][i];

		for(int j = 0 ; j < H ; j++)
			dist[viz][j] = dist[cur][j] + digits[viz][j] - 1;

		DFS( viz , H );
	}
}

void decode(int N, int H) 
{
	for(int i = 1 ; i < N ; i++)
		adj[ read(10) ].push_back( i );

	for(int i = 1 ; i < H ; i++)
		dist[0][i] = read(10);

	for(int i = 0 ; i < N - 1 ; i++)
	{
		lli diffDist = read(56);

		digits[i + 1].push_back( 2 );
		toTernaryBase( diffDist , i + 1 , H );
	}

	DFS( 0 , H );

	for(int i = 0 ; i < N ; i++)
		for(int j = 0 ; j < H ; j++)
			hops( j , i , dist[i][j] );
}

Compilation message (stderr)

encoder.cpp: In function 'void BFS(int, int, bool)':
encoder.cpp:52:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[cur].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:93:8: warning: 'v' may be used uninitialized in this function [-Wmaybe-uninitialized]
    sum = 3*sum + v;
    ~~~~^~~~~~~~~~~

decoder.cpp: In function 'void DFS(int, int)':
decoder.cpp:54:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~

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