Submission #3137

#	Time	Username	Problem	Language	Result	Execution time	Memory
3137		club4208	Saveit (IOI10_saveit)	C++98	100 / 100	584 ms	15080 KiB

encoder

#include<stdio.h>
#include "grader.h"
#include "encoder.h"
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair<int,int>pii;
void encode(int cit, int hab, int way, int *va, int *vb)
{
  vector<int>pat[1000];
  int dist[36][1000];
  for(int i=0;i<way;i++)
    {
      pat[va[i]].push_back(vb[i]);
      pat[vb[i]].push_back(va[i]);
    }
  for(int i=0;i<hab;i++)
    {
      for(int j=0;j<cit;j++)
	{
	  dist[i][j]=-1;
	}
    }
  for(int p=0;p<hab;p++)
    {
      queue<pii>que;
      que.push(make_pair(0,p));
      for(;;)
	{
	  if(que.empty())
	    {
	      break;
	    }
	  pii zan=que.front();
	  que.pop();
	  if(dist[p][zan.second]!=-1)
	    {
	      continue;
	    }
	  dist[p][zan.second]=zan.first;
	  for(int i=0;i<pat[zan.second].size();i++)
	    {
	      if(dist[p][pat[zan.second][i]]==-1)
		{
		  que.push(make_pair(zan.first+1,pat[zan.second][i]));
		}
	    }
	}
    }
  queue<int>que;
  bool flag[1000];
  int par[1000];
  fill(flag,flag+1000,false);
  fill(par,par+1000,1023);
  que.push(0);
  for(;;)
    {
      if(que.empty())
	{
	  break;
	}
      int zan=que.front();
      que.pop();
      if(flag[zan])
	{
	  continue;
	}
      flag[zan]=true;
      for(int i=0;i<pat[zan].size();i++)
	{
	  if(!flag[pat[zan][i]])
	    {
	      que.push(pat[zan][i]);
	      par[pat[zan][i]]=zan;
	    }
	}
    }
  for(int i=1;i<cit;i++)
    {
      for(int j=9;j>=0;j--)
	{
	  encode_bit((par[i]>>j)&1);
	}
    }
  for(int i=0;i<hab;i++)
    {
      for(int j=9;j>=0;j--)
	{
	  encode_bit((dist[i][0]>>j)&1);
	}
    }
  for(int i=0;i<hab;i++)
    {
      int now=0;
      for(int j=1;j<cit;j++)
	{
	  now*=3;
	  if(dist[i][par[j]]==dist[i][j])
	    {
	      now+=0;
	    }
	  if(dist[i][par[j]]==dist[i][j]+1)
	    {
	      now+=1;
	    }
	  if(dist[i][par[j]]==dist[i][j]-1)
	    {
	      now+=2;
	    }
	  if(j%5==0||j==cit-1)
	    {
	      for(;;)
		{
		  if(j%5!=0)
		    {
		      j++;
		      now*=3;
		    }
		  else
		    {
		      break;
		    }
		}
	      for(int k=7;k>=0;k--)
		{
		  encode_bit((now>>k)&1);
		}
	      now=0;
	    }
	}
    }
}

decoder

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include "grader.h"
#include "decoder.h"
using namespace std;
void decode(int cit, int hab)
{
  int par[1000];
  vector<int>ko[1000];
  int st[36];
  par[0]=-1;
  for(int i=1;i<cit;i++)
    {
      int now=0;
      for(int j=0;j<10;j++)
	{
	  now*=2;
	  now+=decode_bit();
	}
      par[i]=now;
      ko[now].push_back(i);
    }
  for(int i=0;i<hab;i++)
    {
      int now=0;
      for(int j=0;j<10;j++)
	{
	  now*=2;
	  now+=decode_bit();
	}
      st[i]=now;
    }
  for(int p=0;p<hab;p++)
    {
      int data[1000];
      data[0]=st[p];
      int cod[1000];
      for(int i=0;i<(cit-1+4)/5;i++)
	{
	  int now=0;
	  for(int j=0;j<8;j++)
	    {
	      now*=2;
	      now+=decode_bit();
	    }
	  for(int j=0;j<5;j++)
	    {
	      if(i*5+1+4-j<cit)
		{
		  cod[i*5+1+4-j]=now%3;
		}
	      now/=3;
	    }
	}
      for(int i=1;i<cit;i++)
	{
	  if(cod[i]==0)
	    {
	      data[i]=0;
	    }
	  if(cod[i]==1)
	    {
	      data[i]=-1;
	    }
	  if(cod[i]==2)
	    {
	      data[i]=1;
	    }
	}
      queue<int>que;
      que.push(0);
      for(;;)
	{
	  if(que.empty())
	    {
	      break;
	    }
	  int zan=que.front();
	  que.pop();
	  if(zan!=0)
	    {
	      data[zan]+=data[par[zan]];
	    }
	  hops(p,zan,data[zan]);
	  for(int i=0;i<ko[zan].size();i++)
	    {
	      que.push(ko[zan][i]);
	    }
	}
    }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:42:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<pat[zan.second].size();i++)
                ~^~~~~~~~~~~~~~~~~~~~~~~
encoder.cpp:70:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int i=0;i<pat[zan].size();i++)
                   ~^~~~~~~~~~~~~~~~

decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:87:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i=0;i<ko[zan].size();i++)
                ~^~~~~~~~~~~~~~~

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