oj.uz

Submission #6988

# Submission time Handle Problem Language Result Execution time Memory
6988 2014-07-12T07:22:20 Z gs13068 Saveit (IOI10_saveit) C++
100 / 100
 336 ms 14100 KB 
#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);
		}
	}
}

#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 14100 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 6 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 9044 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 13 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 38 ms 9108 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 9472 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 70 ms 9980 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 31 ms 9316 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 9508 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 36 ms 9440 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 46 ms 9536 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 32 ms 9496 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 80 ms 10040 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 41 ms 9404 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 36 ms 9452 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 9896 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 85 ms 9964 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 89 ms 10044 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 41 ms 9760 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 80 ms 10456 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 93 ms 10508 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 69 ms 10120 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 121 ms 10732 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 14100 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 6 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 9044 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 13 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 38 ms 9108 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 9472 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 70 ms 9980 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 31 ms 9316 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 9508 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 36 ms 9440 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 46 ms 9536 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 32 ms 9496 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 80 ms 10040 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 41 ms 9404 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 36 ms 9452 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 9896 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 85 ms 9964 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 89 ms 10044 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 41 ms 9760 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 80 ms 10456 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 93 ms 10508 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 69 ms 10120 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 121 ms 10732 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 14100 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 6 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 9044 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 13 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 38 ms 9108 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 9472 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 70 ms 9980 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 31 ms 9316 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 9508 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 36 ms 9440 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 46 ms 9536 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 32 ms 9496 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 80 ms 10040 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 41 ms 9404 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 36 ms 9452 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 9896 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 85 ms 9964 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 89 ms 10044 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 41 ms 9760 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 80 ms 10456 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 93 ms 10508 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 69 ms 10120 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 121 ms 10732 KB Output is correct - 67600 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 336 ms 14100 KB Output is correct - 67600 call(s) of encode_bit()
2 Correct 6 ms 4676 KB Output is correct - 74 call(s) of encode_bit()
3 Correct 33 ms 9044 KB Output is correct - 60840 call(s) of encode_bit()
4 Correct 13 ms 4672 KB Output is correct - 90 call(s) of encode_bit()
5 Correct 38 ms 9108 KB Output is correct - 60840 call(s) of encode_bit()
6 Correct 40 ms 9472 KB Output is correct - 67600 call(s) of encode_bit()
7 Correct 70 ms 9980 KB Output is correct - 67600 call(s) of encode_bit()
8 Correct 31 ms 9316 KB Output is correct - 65194 call(s) of encode_bit()
9 Correct 44 ms 9508 KB Output is correct - 67600 call(s) of encode_bit()
10 Correct 36 ms 9440 KB Output is correct - 67600 call(s) of encode_bit()
11 Correct 46 ms 9536 KB Output is correct - 67600 call(s) of encode_bit()
12 Correct 32 ms 9496 KB Output is correct - 67600 call(s) of encode_bit()
13 Correct 80 ms 10040 KB Output is correct - 67600 call(s) of encode_bit()
14 Correct 41 ms 9404 KB Output is correct - 67600 call(s) of encode_bit()
15 Correct 36 ms 9452 KB Output is correct - 67600 call(s) of encode_bit()
16 Correct 67 ms 9896 KB Output is correct - 67600 call(s) of encode_bit()
17 Correct 85 ms 9964 KB Output is correct - 67600 call(s) of encode_bit()
18 Correct 89 ms 10044 KB Output is correct - 67600 call(s) of encode_bit()
19 Correct 41 ms 9760 KB Output is correct - 67600 call(s) of encode_bit()
20 Correct 80 ms 10456 KB Output is correct - 67600 call(s) of encode_bit()
21 Correct 93 ms 10508 KB Output is correct - 67600 call(s) of encode_bit()
22 Correct 69 ms 10120 KB Output is correct - 67600 call(s) of encode_bit()
23 Correct 121 ms 10732 KB Output is correct - 67600 call(s) of encode_bit()