Submission #1263835

#	Time	Username	Problem	Language	Result	Execution time	Memory
1263835		gustavo_d	Saveit (IOI10_saveit)	C++20	100 / 100	48 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], diffs[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);
  }
}

int calculate_encode(vector<int> grp) {
  int code = 0;
  for (int i=0, pot=1; i<5; i++, pot*=3) {
    code += grp[i] * pot;
    // cerr << '(' << grp[i] << ' ' << pot << ')';
  }
  // cerr << "code=" << code << '\n';
  return code;
}

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++) {
    // cerr << "\n\n\nenvia hub " << h << endl;
    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]];
      diffs[i] = diff;
    }
    for (int i=1; i<n; i+=5) {
      vector<int> grp(5, 0);
      for (int j=0; j<5 and i+j<n; j++) {
        grp[j] = diffs[i+j] + 1;
        // // cerr << grp[j] << ' ';
      }
      send_int(calculate_encode(grp), 8);
    }
  }
  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);
   }
}

vector<int> decode_grp(int code) {
   vector<int> grp(5, 0);
   for (int i=4, pot=81; i>=0; i--, pot /= 3) {
      grp[i] = code / pot;
      code %= pot;
   }
   return grp;
}

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++) {
      // cerr << "\n\n\nrecebe hub " << h << endl;
      for (int i=1; i<n; i+=5) {
         int code = readInt(8);
         vector<int> grp = decode_grp(code);
         for (int j=0; j<5 and i + j < n; j++) {
            int dist = grp[j] - 1;
            // cerr << grp[j] << ' ';
            adjDelta[i+j].emplace_back(pai[i+j], -dist);
            adjDelta[pai[i+j]].emplace_back(i+j, dist);
         }
      }
      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: 25 / 25