Submission #6988

#	Time	Username	Problem	Language	Result	Execution time	Memory
6988		gs13068	Saveit (IOI10_saveit)	C++98	100 / 100	336 ms	14100 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <vector>

static std::vector<int> G[1000];
static int P[1000];
static int Q[1000],QN;
static int D[1000];

static void send(int x,int y){while(x--)encode_bit((y>>x)&1);}

void encode(int N, int H, int E, int A[], int B[])
{
	int i,j,k,t;
	for(i=0;i<N;i++)G[i].clear();
    for(i=0;i<E;i++)
	{
		G[A[i]].push_back(B[i]);
		G[B[i]].push_back(A[i]);
	}
	QN=0;
	for(j=0;j<N;j++)P[j]=-1;
    Q[QN++]=0;
    P[0]=0;
    for(j=0;j<N;j++)for(k=0;k<G[Q[j]].size();k++)if(P[G[Q[j]][k]]<0)
    {
        Q[QN++]=G[Q[j]][k];
        P[G[Q[j]][k]]=Q[j];
	}
	for(j=0;j<N;j++)send(10,P[j]);
    for(i=0;i<H;i++)
	{
		QN=0;
		for(j=0;j<N;j++)D[j]=-1;
        Q[QN++]=i;
        D[i]=0;
        for(j=0;j<N;j++)for(k=0;k<G[Q[j]].size();k++)if(D[G[Q[j]][k]]<0)
		{
			Q[QN++]=G[Q[j]][k];
			D[G[Q[j]][k]]=D[Q[j]]+1;
		}
		for(j=0;j<(N+4)/5;j++)
		{
			t=0;
			for(k=0;k<5;k++)
			{
				t*=3;
                if(j*5+k<N)t+=D[j*5+k]-D[P[j*5+k]]+1;
			}
			send(8,t);
		}
	}
}

decoder

#include "grader.h"
#include "decoder.h"
#include <vector>

static std::vector<int> G[1000];
static int P[1000];
static int A[1000][1000];
static int Q[1000],QN;
static int D[1000];

static int receive(int x){int y;for(y=0;x--;y|=decode_bit())y<<=1;return y;}

void decode(int N,int H)
{
	int i,j,k,t;
	for(i=0;i<N;i++)for(j=0;j<N;j++)A[i][j]=0;
    for(i=0;i<N;i++)
	{
		P[i]=receive(10);
        G[i].push_back(P[i]);
        G[P[i]].push_back(i);
	}
    for(i=0;i<H;i++)
	{
		for(j=0;j<(N+4)/5;j++)
		{
			t=receive(8);
			for(k=4;k>=0;k--)
			{
				if(j*5+k<N)
				{
					A[P[j*5+k]][j*5+k]=t%3-1;
					A[j*5+k][P[j*5+k]]=1-t%3;
				}
                t/=3;
			}
		}
		QN=0;
		for(j=0;j<N;j++)D[j]=-1;
		Q[QN++]=i;
        D[i]=0;
        for(j=0;j<N;j++)for(k=0;k<G[Q[j]].size();k++)if(D[G[Q[j]][k]]<0)
		{
			Q[QN++]=G[Q[j]][k];
			D[G[Q[j]][k]]=D[Q[j]]+A[Q[j]][G[Q[j]][k]];
		}
		for(j=0;j<N;j++)hops(i,j,D[j]);
	}
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:25:30: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(j=0;j<N;j++)for(k=0;k<G[Q[j]].size();k++)if(P[G[Q[j]][k]]<0)
                             ~^~~~~~~~~~~~~~~
encoder.cpp:37:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<N;j++)for(k=0;k<G[Q[j]].size();k++)if(D[G[Q[j]][k]]<0)
                                 ~^~~~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:42:34: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
         for(j=0;j<N;j++)for(k=0;k<G[Q[j]].size();k++)if(D[G[Q[j]][k]]<0)
                                 ~^~~~~~~~~~~~~~~

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