Submission #1180144

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180144		n3rm1n	Saveit (IOI10_saveit)	C++20	50 / 100	54 ms	8776 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1005, maxh = 40;
int p;
vector < int > g[maxn];
vector < pair < int, int > > edges;
int distt[maxh][maxn], parr[maxn];
void bfs(int start, int n)
{
   // cout << "run " << start << endl;
    for (int i = 0; i < n; ++ i)
        distt[start][i] = -1;
    queue < int > q;
    q.push(start);
    distt[start][start] = 0;
    while(!q.empty())
    {
        int w = q.front();
       // cout << "w is " << w << endl;
        q.pop();
        for (auto nb: g[w])
        {
           // cout << nb << endl;
            if(distt[start][nb] != -1)continue;
            distt[start][nb] = distt[start][w] + 1;
          //  cout << "?"<< distt[start][nb] << endl;
            if(start == 0)parr[nb] = w;
            q.push(nb);
        }
    }
}
int curr_bit = 0;
void code_bits(int x)
{
    for (int i = 0; i < 10; ++ i)
    {
        if(x & (1 << i))
        {
            encode_bit(1);
        }
        else encode_bit(0);
        curr_bit++;
    }
}
void code_bits3(int x)
{
    for (int i = 0; i < 2; ++ i)
    {
        if(x & (1 << i))
        {
            encode_bit(1);
        }
        else encode_bit(0);
        curr_bit++;
    }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
  //  cout << "in encode" << endl;
  int n = nv;
  int h = nh;
  p = ne;

  for (int i = 0; i < p; ++ i)
  {
      int u = v1[i];
      int v = v2[i];
      edges.pb(make_pair(u, v));
      g[u].pb(v);
      g[v].pb(u);
     // cout << u << " " << v<<endl;
  }
  for (int i = 0; i < h; ++ i)
    bfs(i, n);
  for (int i = 1; i < n; ++ i)
  {
      //if(!parr[i])continue;
      //cout << i << " "<<parr[i] << endl;
      code_bits(parr[i]);
  }
  for (int i = 0; i < h; ++ i)
  {
      for (int j = 1; j < n; ++ j)
      {
        //  cout << "dist btween " << i << " " << j << " is " << distt[i][j] << endl;
          if(distt[i][j] == distt[i][parr[j]])code_bits3(0);
          else if(distt[i][j] == distt[i][parr[j]] - 1)code_bits3(1);
          else code_bits3(2);
      }
  }
 // cout << "ended " << endl;
  return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxnn = 1005;
int n, hh;
int par[maxnn];
vector < int > u[maxnn];
int dist[maxnn][maxnn], change[maxnn][maxnn];
void dfs(int beg, int d)
{
    dist[0][beg] = d-1;
    dist[beg][0] = d-1;
    for (auto nb: u[beg])
    {
        dfs(nb, d + 1);
    }
}

void solve(int curr)
{
    for (int i = 0; i < hh; ++ i)
        hops(i, curr, dist[i][curr]);

    for (auto child: u[curr])
    {

        for (int i = 0; i < hh; ++ i)
        {
            //cout << i << " " << hh << endl;
            dist[i][child] = dist[i][curr] + change[i][child];
        }
        solve(child);
    }
}
void decode(int nv, int nh)
{
   n = nv;
   hh = nh;
   for (int i = 1; i < n; ++ i)
   {

       for (int bit = 0; bit < 10; ++ bit)
       {
           int curr = decode_bit();
           if(curr)par[i] = (par[i] | (1 << bit));
       }
       //cout << i << " !! " << par[i] << endl;
   }
   for (int i = 1; i < n; ++ i)
   {
       u[par[i]].pb(i);
   }

   dfs(0, 1);
  // cout << "dfs ended " << endl;
   for (int i = 0; i < hh; ++ i)
   {
       for (int j = 1; j < n; ++ j)
       {
           //cout << i << " " << j << endl;
           int fbit, sbit;
           fbit = decode_bit();
           sbit = decode_bit();

           int number = 0;
           if(fbit)number += 1;
           if(sbit)number += 2;
           if(number == 0)change[i][j] = 0;
           else if(number == 1)change[i][j] = -1;
           else change[i][j] = 1;
         //  cout << fbit << ", " << sbit << "-> " << number << endl;
         //  cout << "change " << i << " " << j << " -> " << number << endl;
       }
   }
  // cout << "solve starting " << endl;
   solve(0);

}

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