Submission #1180137

#	Time	Username	Problem	Language	Result	Execution time	Memory
1180137		n3rm1n	Saveit (IOI10_saveit)	C++20	0 / 100	41 ms	7600 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)
{
    queue < int > q;
    q.push(start);
    distt[start][start] = 0;
    while(!q.empty())
    {
        int w = q.front();
        q.pop();
        for (auto nb: g[w])
        {
            if(distt[start][nb] != -1)continue;
            distt[start][nb] = distt[start][w] + 1;
            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(curr_bit);
        }
        curr_bit++;
    }
}
void code_bits3(int x)
{
    for (int i = 0; i < 2; ++ i)
    {
        if(x & (1 << i))
        {
            encode_bit(curr_bit);
        }
        curr_bit++;
    }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
  int n = nv;
  int h = nh;
  p = ne;
  memset(distt, -1, sizeof(distt));
  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);
  }
  for (int i = 0; i < h; ++ i)
    bfs(i);
  for (int i = 1; i < n; ++ i)
  {
      if(!parr[i])continue;
      code_bits(parr[i]);
  }
  for (int i = 0; i < h; ++ i)
  {
      for (int j = 1; j < n; ++ j)
      {
          if(distt[i][j] == distt[parr[i]][j])code_bits3(0);
          else if(distt[i][j] == distt[i][parr[j]] - 1)code_bits3(1);
          else code_bits3(2);
      }
  }
  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;
    dist[beg][0] = d;
    for (auto nb: u[beg])
    {
        dfs(nb, d + 1);
    }
}

void solve(int curr)
{
    for (auto child: u[curr])
    {
        for (int i = 0; i < hh; ++ i)
        {
            dist[i][child] = dist[i][curr] + change[i][child];
            hops(i, child, dist[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));
       }
   }
   for (int i = 0; i < n; ++ i)
   {
       u[par[i]]. pb(i);
   }

   dfs(0, 1);
   for (int i = 0; i < hh; ++ i)
   {
       for (int j = 0; j < n; ++ j)
       {
           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;
       }
   }
   solve(0);

}

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