Submission #860534

#	Time	Username	Problem	Language	Result	Execution time	Memory
860534		nguyentunglam	Saveit (IOI10_saveit)	C++17	50 / 100	221 ms	20524 KiB

encoder

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

const int N = 1010;

int f[N];

vector<int> adj[N];

void encode(int n, int h, int p, int *v1, int *v2){
   int T = log2(n) + 1;

   for(int i = 0; i < p; i++) {
      adj[v1[i]].push_back(v2[i]);
      adj[v2[i]].push_back(v1[i]);
   }

   for(int i = 0; i < h; i++) {
      for(int j = 0; j < n; j++) f[j] = -1;
      f[i] = 0;
      queue<int> q; q.push(i);
      while (!q.empty()) {
         int u = q.front(); q.pop();
         for(int &v : adj[u]) if (f[v] < 0) {
            f[v] = f[u] + 1;
            q.push(v);
         }
      }


      for(int j = 0; j < n; j++) {
         for(int k = 0; k < T; k++) encode_bit(f[j] >> k & 1);
      }
   }
}

decoder

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

void decode(int n, int h) {
   int T = log2(n) + 1;

   for(int i = 0; i < h; i++) for(int j = 0; j < n; j++) {
      int ans = 0;
      for(int k = 0; k < T; k++) if (decode_bit()) ans |= (1 << k);
//      if (i == 0 && j == 1) cout << ans << endl;
      hops(i, j, ans);
//      cout << i << " " << j << " " << ans << endl;
   }
}

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