Submission #60860

#	Time	Username	Problem	Language	Result	Execution time	Memory
60860		win11905	Saveit (IOI10_saveit)	C++11	0 / 100	331 ms	262148 KiB

encoder

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

const int N = 1005;

static vector<int> g[N], ng[N];
static int d[N];
static bool chk[N];
static int ntsp[N];

void addShort(int u) {
  for(int i = 9; ~i; --i) encode_bit(u >> i & 1);
}

static void dfs(int u, int p) {
  if(u) addShort(p), ng[u].emplace_back(p);
  chk[u] = true;
  for(int v : g[u]) if(v != p && !chk[v]) ng[u].emplace_back(v), dfs(v, u);
}

// 0 -1 1
void process(int u, int p) {
  ntsp[u] = (d[u] == d[p] ? 0 : (d[u] < d[p] ? 1 : 2));
  for(int v : ng[u]) if(v != p) process(v, u);
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  for(int i = 0; i < ne; ++i)
    g[v1[i]].emplace_back(v2[i]), g[v2[i]].emplace_back(v1[i]);
  dfs(0, -1);
  for(int i = 0; i < nh; ++i) {
    fill_n(d, N, (int)1e9);
    queue<int> Q; Q.emplace(i), d[i] = 0;
    while(!Q.empty()) {
      int u = Q.front(); Q.pop();
      for(int v : g[u]) if(d[v] > d[u] + 1) 
        d[v] = d[u] + 1, Q.emplace(v);
    }
    process(i, i);
    for(int i = 0; i < 200; ++i) {
      int sum = 0;
      for(int j = 4; ~j; --j) sum = sum * 3 + ntsp[5*i+j];
      for(int j = 7; ~j; --j) encode_bit(sum >> j & 1);
    }
  } 
  return;
}

decoder

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

const int N = 1e3+5;

static vector<int> g[N];
static int d[N], v[N], z[N];

int getInt(int len) {
    int sum = 0;
    for(int i = 0; i < len; ++i) sum = (sum<<1) + decode_bit();
    return sum;
}

static void dfs(int u, int p) {
    d[u] = d[p] + v[u];
    for(int v : g[u]) if(v != p) dfs(v, u);
}

void decode(int nv, int nh) {
    for(int i = 1; i < nv; ++i) {
        int p = getInt(10);
        g[p].emplace_back(i), g[i].emplace_back(p);
    }
    for(int i = 0; i < nh; ++i) {
        d[i] = 0;
        for(int j = 0; j < 200; ++j) {
            int ret = getInt(8);
            for(int k = 0; k < 5; ++k) z[j*5+k] = ret % 3, ret /= 3;
        }
        for(int j = 0; j < 1000; ++j) v[j] = (z[j] == 0 ? 0 : (z[j] == 1 ? -1 : 1));
        dfs(i, i);
        for(int j = 0; j < nv; ++j) hops(i, j, d[j]);
    }
    return;
}

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