Submission #1258642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1258642		gustavo_d	Saveit (IOI10_saveit)	C++20	75 / 100	51 ms	5952 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;
const int MAXH = 36;

vector<int> adjE[MAXN];
bool visE[MAXN];
int distE[MAXN], paiE[MAXN], lastDistE[MAXN];

int n;

void bfs(int src, bool updatePai) {
  for (int i=0; i<n; i++) {
    visE[i] = false;
  }
  visE[src] = true; distE[src] = 0;
  queue<int> visit; visit.push(src);
  while (!visit.empty()) {
    int v = visit.front(); visit.pop();
    for (int viz : adjE[v]) {
      if (visE[viz]) continue;
      visE[viz] = true;
      distE[viz] = distE[v] + 1;
      if (updatePai) {
        paiE[viz] = v;
        // cout << "pai: " << v << " de " << viz << endl;
      }
      visit.push(viz);
    }
  }
}

void send_int(int val, int bits) {
  // cout << "envia" << val << endl;
  for (int b=0; b<bits; b++) {
    encode_bit(((1 << b) & val) != 0);
  }
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  n = nv;
  for (int i=0; i<ne; i++) {
    int u = v1[i], v = v2[i];
    adjE[u].push_back(v);
    adjE[v].push_back(u);
  }

  bfs(0, true);
  for (int i=1; i<n; i++) {
    // cout << paiE[i] << endl;
    send_int(paiE[i], 10);
  }
  for (int h=1; h<nh; h++) {
    for (int i=0; i<n; i++) lastDistE[i] = distE[i];
    bfs(h, false);
    for (int i=1; i<n; i++) {
      int diff = distE[i] - distE[paiE[i]];
      assert(abs(diff) <= 1);
      // cout << i << ':' << distE[i] << ' ' << distE[paiE[i]] << endl;
      if (diff == -1) send_int(0, 2);
      else if (diff == 0) send_int(1, 2);
      else send_int(2, 2);
    }
    // cout << endl;
  }
  return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 1000;

vector<int> adj[MAXN];
vector<pair<int, int>> adjDelta[MAXN];
bool vis[MAXN];
int dist[MAXN], pai[MAXN];

int readInt(int bits) {
   int res = 0;

   for (int b=0; b<bits; b++) {
      if (decode_bit()) res += (1 << b);
   }

   // cout << "recebe " << res << endl;

   return res;
}

void dfs(int v) {
   for (int viz : adj[v]) {
      dist[viz] = dist[v] + 1;
      dfs(viz);
   }
}

void dfsDelta(int v) {
   vis[v] = true;
   for (auto [viz, delta] : adjDelta[v]) {
      if (vis[viz]) continue;
      dist[viz] = dist[v] + delta;
      dfsDelta(viz);
   }
}

void decode(int nv, int nh) {
   int n = nv;
   for (int i=1; i<n; i++) {
      pai[i] = readInt(10);
      adj[pai[i]].push_back(i);
   }

   dist[0] = 0;
   dfs(0);
   for (int i=0; i<n; i++) hops(0, i, dist[i]);

   for (int h=1; h<nh; h++) {
      for (int i=1; i<n; i++) {
         int id = readInt(2);
         int dist = ( // [i] - [pai[i]]
            id == 0 ? -1 : (
               id == 1 ? 0 : 1
            )
         );
         adjDelta[i].emplace_back(pai[i], -dist);
         adjDelta[pai[i]].emplace_back(i, dist);
         // cout << i << '>' << pai[i] << ' ' << -dist << endl;
      }
      dist[h] = 0;
      dfsDelta(h);
      for (int i=0; i<n; i++) hops(h, i, dist[i]);
      for (int i=0; i<n; i++) {
         vis[i] = false;
         adjDelta[i].clear();
      }
      // cout << endl << endl;
   }
}

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