Submission #513862

# Submission time Handle Problem Language Result Execution time Memory
513862 2022-01-17T19:25:16 Z jerzyk Saveit (IOI10_saveit) C++14
Compilation error
0 ms 0 KB
#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
 
typedef long long ll;
using namespace std;
const int N = 1000 + 7;
vector<int>ed[N];
int tab[38][N], wsk[N];
 
ll Return3(int v, int h)
{
  ll w = 0LL, m, pot = 1LL;
  for(int i = 1; i <= h; ++i)
  {
    m = 0LL;
    if(tab[i][v] == tab[i][wsk[v]])
      m = 1LL;
    if(tab[i][v] > tab[i][wsk[v]])
      m = 2LL;
    w += m * pot;
    pot *= 3LL;
  }
  return w;
}

void PrintBits(ll x, int l)
{
  for(int i = 1; i <= l; ++i)
  {
    encode_bit((int)(x % 2LL));
    //cout << x % 2LL;
    x /= 2LL;
  }
}
 
void DFS(int v)
{
  for(int i = 0; i < (int)ed[v].size(); ++i)
  {
    if(wsk[ed[v][i]] == 0)
    {
      wsk[ed[v][i]] = v;
      DFS(ed[v][i]);
    }
  }
}
 
void BFS(int n, int s)
{
  int v;
  queue<int> q;
  for(int i = 1; i <= n; ++i)
    tab[s][i] = N * 2;
  tab[s][s] = 0;
  q.push(s);
  while(q.size() > 0)
  {
    v = q.front();
    q.pop();
    for(int i = 0; i < (int)ed[v].size(); ++i)
    {
      if(tab[s][ed[v][i]] > tab[s][v] + 1)
      {
        tab[s][ed[v][i]] = tab[s][v] + 1;
        q.push(ed[v][i]);
      }
    }
  }
}

void encode(int n, int h, int m, int* a, int* b)
{
  for(int i = 0; i < m; ++i)
  {
    ed[a[i] + 1].push_back(b[i] + 1);
    ed[b[i] + 1].push_back(a[i] + 1);
  }
  for(int i = 1; i <= h; ++i)
    BFS(n, i);
  wsk[1] = 1;
  DFS(1);
  for(int i = 2; i <= h; ++i)
    PrintBits(tab[i][1], 10);
  for(int i = 2; i <= n; ++i)
  {
    PrintBits(wsk[i], 10);       
    PrintBits(Return3(i, h), 58);
  }
}

/*
int main()
{
  int n, h, m;
  cin >> n >> m >> h;
  for(int i = 0; i < m; ++i)
  {
    int a, b;
    cin >> a >> b;
    ed[a + 1].push_back(b + 1);
    ed[b + 1].push_back(a + 1);
  }
  for(int i = 1; i <= h; ++i)
    BFS(n, i);
  wsk[1] = 1;
  DFS(1);
  for(int i = 2; i <= h; ++i)
    PrintBits(tab[i][1], 10);
  for(int i = 2; i <= n; ++i)
  {
    PrintBits(wsk[i], 10);
    //cout << i << " " << wsk[i] << " " << tab[1][i] << " " << Return3(i, h) << "\n";  
    PrintBits(Return3(i, h), 58);
  }
  cout << "\n";
  return 0;
}*/
//#include "grader.h"
//#include "decoder.h"
#include<bits/stdc++.h>
 
using namespace std;
typedef long long ll;
const int N = 1000 + 7;
int odl[37][N], dod[37][N], wsk[N];
vector<int>ed[N];
 
void DFS(int v, int h)
{
   for(int i = 1; i <= h; ++i)
      if(v != 1)
         odl[i][v] = dod[i][v] + odl[i][wsk[v]];
    for(int i = 0; i < (int)ed[v].size(); ++i)
      DFS(ed[v][i], h);
}
 
void Dod(ll l, int v, int h)
{
   //cout << v << " " << l << "\n";
   for(int i = 1; i <= h; ++i)
   {
      if(l % 3LL == 0LL)
         dod[i][v] = -1;
      if(l % 3LL == 2LL)
         dod[i][v] = 1;
      l /= 3LL;
   }
}
 
ll ReadBits(int n)
{
   ll w = 0LL, b, pot = 1LL;
   //char z;
   for(int i = 0; i < n; ++i)
   {
      b = decode_bit();
      //cin >> z; b = z - '0';
      w += pot * b;
      pot *= 2LL;
   }
   return w;
}
 
void decode(int n, int h)
{
   for(int i = 2; i <= h; ++i)
     odl[i][1] = ReadBits(10);
   for(int i = 2; i <= n; ++i)
   {
      wsk[i] = ReadBits(10);
      ed[wsk[i]].push_back(i);
      Dod(ReadBits(58), i, h);
   }
   DFS(1, h);
   for(int i = 1; i <= h; ++i)
      for(int j = 1; j <= n; ++j)
         hops(i - 1, j - 1, odl[i][j]);
}

/*
int main()
{
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   int n, h;
   cin >> n >> h;
   decode(n, h);

   return 0;
}*/

Compilation message

decoder.cpp: In function 'll ReadBits(int)':
decoder.cpp:39:11: error: 'decode_bit' was not declared in this scope; did you mean 'femode_t'?
   39 |       b = decode_bit();
      |           ^~~~~~~~~~
      |           femode_t
decoder.cpp: In function 'void decode(int, int)':
decoder.cpp:60:10: error: 'hops' was not declared in this scope
   60 |          hops(i - 1, j - 1, odl[i][j]);
      |          ^~~~