Submission #774108

#	Time	Username	Problem	Language	Result	Execution time	Memory
774108		Amylopectin	Saveit (IOI10_saveit)	C++14	100 / 100	159 ms	11404 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <vector>
#include <stdio.h>
#include <queue>
using namespace std;
const int mxn = 2e3 + 10;
queue<int> qu;
vector<int> pat[mxn] = {};
int u[mxn] = {},par[mxn] = {},dist[mxn][mxn] = {},pom[mxn][mxn] = {}
,thr[5] = {1,3,9,27,81};
int re(int cn,int he,int rou)
{
  int i,j,fn;
  u[cn] = rou;
  for(i=0; i<pat[cn].size(); i++)
  {
    fn = pat[cn][i];
    if(u[fn] != rou)
    {
      dist[he][fn] = dist[he][cn] + 1;
      re(fn,he,rou);
    }
  }
  return 0;
}
int re2(int cn,int he,int rou)
{
  int i,j,fn;
  u[cn] = rou;
  for(i=0; i<pat[cn].size(); i++)
  {
    fn = pat[cn][i];
    if(fn != par[cn] && par[fn] != cn)
    {
      continue;
    }
    if(u[fn] != rou)
    {
      if(fn == par[cn])
      {
        pom[he][cn] = dist[he][fn] - dist[he][cn];
      }
      else 
      {
        pom[he][fn] = dist[he][fn] - dist[he][cn];
      }
      re2(fn,he,rou);
    }
  }
  return 0;
}
void encode(int n, int nh, int m, int *frr, int *too)
{
  int i,j,k,cn,cm,fn,fm;
  for(i=0; i<m; i++)
  {
    pat[frr[i]].push_back(too[i]);
    pat[too[i]].push_back(frr[i]);
  }
  dist[0][0] = 0;
    par[0] = -1;
    u[0] = 1;
qu.push(0);
while(!qu.empty())
{
  cn = qu.front();
  qu.pop();
  for(j=0; j<pat[cn].size(); j++)
  {
    fn = pat[cn][j];
    if(u[fn] == 0)
    {
      u[fn] = 1;
      dist[0][fn] = dist[0][cn] + 1;
      par[fn] = cn;
      qu.push(fn);
    }
  }
}
    // re(0,0,1);
      for(j=1; j<n; j++)
      {
        for(k=0; k<10; k++)
        {
          if((1<<k) & par[j])
          {
            encode_bit(1);
          }
          else 
          {
            encode_bit(0);
          }
        }
      }
  for(i=1; i<nh; i++)
  {
    dist[i][i] = 0;
    u[i] = i+1;
    // re(i,i,i+1);
    // dist[0][0] = 0;
    // par[0] = -1;
qu.push(i);
while(!qu.empty())
{
  cn = qu.front();
  qu.pop();
  for(j=0; j<pat[cn].size(); j++)
  {
    fn = pat[cn][j];
    if(u[fn] != i+1)
    {
      u[fn] = i+1;
      dist[i][fn] = dist[i][cn] + 1;
      // par[fn] = cn;
      qu.push(fn);
    }
  }
}
  }
  for(i=1; i<nh; i++)
  {
    re2(i,i,i+1);
    for(j=1; j<n; j+=5)
    {
      cn = 0;
      for(k=0; k<5; k++)
      {
        cn += (pom[i][j+k] + 1) * thr[k];
      }
      for(k=0; k<8; k++)
      {
          if((1<<k) & cn)
          {
            encode_bit(1);
          }
          else 
          {
            encode_bit(0);
          }
      }
    }
  }
  return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include <vector>
#include <stdio.h>
#include <queue>
using namespace std;
const int mxm = 2e3 + 10;
// queue<int> qu;
vector<int> pat2[mxm] = {};
int u2[mxm] = {},par2[mxm] = {},dist2[mxm][mxm] = {},pom2[mxm][mxm] = {}
,thr2[5] = {1,3,9,27,81},acou = 0;
int re3(int cn,int he,int rou)
{
  int i,j,fn;
  u2[cn] = rou;
  for(i=0; i<pat2[cn].size(); i++)
  {
    fn = pat2[cn][i];
    if(u2[fn] != rou)
    {
      dist2[he][fn] = dist2[he][cn] + 1;
      acou ++;
      // hops(he,fn,0);
      re3(fn,he,rou);
    }
  }
  return 0;
}
int re4(int cn,int he,int rou)
{
  int i,j,fn;
  u2[cn] = rou;
  for(i=0; i<pat2[cn].size(); i++)
  {
    fn = pat2[cn][i];
    if(fn != par2[cn] && par2[fn] != cn)
    {
      continue;
    }
    if(u2[fn] != rou)
    {
      if(fn == par2[cn])
      {
         dist2[he][fn] = dist2[he][cn] + pom2[he][cn];
         // = dist2[he][fn] - dist2[he][cn];
      }
      else 
      {
         dist2[he][fn] = dist2[he][cn] + pom2[he][fn];
      //   pom2[he][fn] = dist2[he][fn] - dist2[he][cn];
      }
      acou ++;
      // hops(he,fn,dist2[he][fn]);
      re4(fn,he,rou);
    }
  }
  return 0;
}
void decode(int n, int nh) 
{
   int i,j,k,cn,cm,fn,fm;
   for(i=1; i<n; i++)
   {
      cn = 0;
      for(j=0; j<10; j++)
      {
         cn += (decode_bit() << j);
      }
      par2[i] = cn;
      pat2[i].push_back(cn);
      pat2[cn].push_back(i);
   }
  dist2[0][0] = 0;
  acou ++;
//   hops(0,0,0);
  re3(0,0,1);
// qu.push(0);
// while(!qu.empty())
// {
//   cn = qu.front();
//   qu.pop();
//   for(j=0; j<pat[cn].size(); j++)
//   {
//     fn = pat[cn][j];
//     if(u[fn] == 0)
//     {
//       u[fn] = 1;
//       dist[0][fn] = dist[0][cn] + 1;
//       par[fn] = cn;
//       qu.push(fn);
//     }
//   }
// }
    // re(0,0,1);
      // for(j=1; j<n; j++)
      // {
      //   for(k=0; k<10; k++)
      //   {
      //     if((1<<k) & par[j])
      //     {
      //       encode_bit(1);
      //     }
      //     else 
      //     {
      //       encode_bit(0);
      //     }
      //   }
      // }
  for(i=1; i<nh; i++)
  {
   for(j=1; j<n; j+=5)
   {
      cn = 0;
      for(k=0; k<8; k++)
      {
         cn += (decode_bit() << k);
      }
      for(k=0; k<5; k++)
      {
         pom2[i][j+k] = cn%3 - 1;
         cn /= 3;
      }
   }
    dist2[i][i] = 0;
    acou ++;
   //  hops(i,i,0);
    re4(i,i,i+1);
  }
//   if(acou != n*nh)
//   {
//    printf("acou incorrect %d\n",acou);
//   }
  for(i=0; i<nh; i++)
  {
   for(j=0; j<n; j++)
   {
      hops(i,j,dist2[i][j]);
   }
  }
//   for(i=1; i<nh; i++)
//   {
//     re2(i,i,i+1);
//     for(j=1; j<n; j+=5)
//     {
//       cn = 0;
//       for(k=0; k<5; k++)
//       {
//         cn += (pom[i][j+k] + 1) * thr[k];
//       }
//       for(k=0; k<8; k++)
//       {
//           if((1<<k) & cn)
//           {
//             encode_bit(1);
//           }
//           else 
//           {
//             encode_bit(0);
//           }
//       }
//     }
//   }
  return;
   // int a = decode_bit();
   // int b = decode_bit();
   // hops(0,0,0);
   // hops(1,2,3);
}

Compilation message (stderr)

encoder.cpp: In function 'int re(int, int, int)':
encoder.cpp:16:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(i=0; i<pat[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~
encoder.cpp:14:9: warning: unused variable 'j' [-Wunused-variable]
   14 |   int i,j,fn;
      |         ^
encoder.cpp: In function 'int re2(int, int, int)':
encoder.cpp:31:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |   for(i=0; i<pat[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~
encoder.cpp:29:9: warning: unused variable 'j' [-Wunused-variable]
   29 |   int i,j,fn;
      |         ^
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:69:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   69 |   for(j=0; j<pat[cn].size(); j++)
      |            ~^~~~~~~~~~~~~~~
encoder.cpp:108:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |   for(j=0; j<pat[cn].size(); j++)
      |            ~^~~~~~~~~~~~~~~
encoder.cpp:55:16: warning: unused variable 'cm' [-Wunused-variable]
   55 |   int i,j,k,cn,cm,fn,fm;
      |                ^~
encoder.cpp:55:22: warning: unused variable 'fm' [-Wunused-variable]
   55 |   int i,j,k,cn,cm,fn,fm;
      |                      ^~

decoder.cpp: In function 'int re3(int, int, int)':
decoder.cpp:16:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   16 |   for(i=0; i<pat2[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~~
decoder.cpp:14:9: warning: unused variable 'j' [-Wunused-variable]
   14 |   int i,j,fn;
      |         ^
decoder.cpp: In function 'int re4(int, int, int)':
decoder.cpp:33:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   33 |   for(i=0; i<pat2[cn].size(); i++)
      |            ~^~~~~~~~~~~~~~~~
decoder.cpp:31:9: warning: unused variable 'j' [-Wunused-variable]
   31 |   int i,j,fn;
      |         ^
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:61:17: warning: unused variable 'cm' [-Wunused-variable]
   61 |    int i,j,k,cn,cm,fn,fm;
      |                 ^~
decoder.cpp:61:20: warning: unused variable 'fn' [-Wunused-variable]
   61 |    int i,j,k,cn,cm,fn,fm;
      |                    ^~
decoder.cpp:61:23: warning: unused variable 'fm' [-Wunused-variable]
   61 |    int i,j,k,cn,cm,fn,fm;
      |                       ^~

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