Submission #932870

#	Time	Username	Problem	Language	Result	Execution time	Memory
932870		nguyentunglam	Saveit (IOI10_saveit)	C++17	100 / 100	536 ms	25468 KiB

encoder

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


namespace ENCODE {

const int NN = 1010;

int n, h;

int p[NN], d[NN][NN];

vector<int> adj[NN], _adj[NN];

void dfs(int u) {
  queue<int> q;
  for(int j = 0; j < n; j++) d[u][j] = -1;
  d[u][u] = 0;
  q.push(u);
  while (!q.empty()) {
    int x = q.front(); q.pop();
    for(int &y : adj[x]) if (d[u][y] < 0) {
      d[u][y] = d[u][x] + 1;
      q.push(y);
    }
  }
  if (u) {
    long long val = 0;
    for(int j = 0; j < h; j++) {
      assert(abs(d[u][j] - d[p[u]][j]) <= 1);
      val = val * 3 + d[u][j] - d[p[u]][j] + 1;
    }
    for(int j = 0; j < 58; j++) encode_bit(val >> j & 1);
  }

  for(int &v : _adj[u]) dfs(v);
}

void encode(int N, int H, int m, int *v1, int *v2){
  n = N;
  h = H;
  for(int i = 0; i < m; i++) {
    adj[v1[i]].push_back(v2[i]);
    adj[v2[i]].push_back(v1[i]);
  }

  queue<int> q;
  q.push(0);
  for(int i = 1; i < n; i++) p[i] = -1;

  while (!q.empty()) {
    int u = q.front(); q.pop();
    for(int &v : adj[u]) if (p[v] < 0) {
      p[v] = u;
      q.push(v);
    }
  }

  for(int i = 1; i < n; i++) {
    for(int j = 0; j < 10; j++) encode_bit(p[i] >> j & 1);
    _adj[p[i]].push_back(i);
  }

  dfs(0);
}
}

void encode(int N, int H, int m, int *v1, int *v2) {
  ENCODE::encode(N, H, m, v1, v2);
}

decoder

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

namespace DECODE {

const int NN = 1010;

int n, h;

int d[NN][NN], p[NN];

vector<int> adj[NN];

void dfs(int u) {
  if (u) {
    long long val = 0;
    for(int j = 0; j < 58; j++) if (decode_bit()) val |= (1LL << j);
    for(int j = h - 1; j >= 0; j--) {
      int diff = val % 3;
      d[u][j] = diff + d[p[u]][j] - 1;
      val /= 3;
    }
  }
  for(int j = 0; j < h; j++) {
    hops(j, u, d[u][j]);
  }
  for(int &v : adj[u]) dfs(v);
}

void decode(int nv, int nh) {
  n = nv;
  h = nh;
  for(int i = 1; i < n; i++) {
    for(int j = 0; j < 10; j++) if (decode_bit()) p[i] |= (1 << j);
    adj[p[i]].push_back(i);
  }

  for(int j = 1; j < h; j++) {
    int x = j;
    while (x) {
      d[0][j]++;
      x = p[x];
    }
  }

  dfs(0);
}
}

void decode(int nv, int nh)  {
  DECODE::decode(nv, nh);
}

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