Submission #1221241

#	Time	Username	Problem	Language	Result	Execution time	Memory
1221241		abczz	Saveit (IOI10_saveit)	C++20	100 / 100	49 ms	9148 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <iostream>
#include <vector>
#include <queue>
#include <array>
#include <algorithm>
#define ll long long

using namespace std;

queue <ll> Q;
vector <ll> adj[1000];
vector <array<ll, 2>> E, V;
array<ll, 9> cnt;
bool B[9];
ll dist[1000], P[1000];
void bfs(ll x) {
  Q.push(x);
  for (int i=0; i<1000; ++i) dist[i] = 1e18, P[i] = -1;
  dist[x] = 0;
  while (!Q.empty()) {
    auto u = Q.front();
    Q.pop();
    for (auto v : adj[u]) {
      if (dist[v] == (ll)1e18) dist[v] = dist[u]+1, P[v] = u, Q.push(v);
    }
  }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
  E.clear();
  for (int i=0; i<nv; ++i) adj[i].clear();
  for (int i=0; i<ne; ++i) {
    adj[v1[i]].push_back(v2[i]);
    adj[v2[i]].push_back(v1[i]);
  }
  bfs(0);
  for (int i=1; i<nv; ++i) {
    E.push_back({P[i], i});
    for (int j=0; j<10; ++j) {
      if (P[i] & (1LL<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }
  if (nh == 1) return;
  vector <ll> F;
  for (int i=1; i<nh; ++i) {
    bfs(i);
    for (auto [u, v] : E) {
      F.push_back(dist[u]-dist[v]);
    }
  }
  if ((F.size() & 1)) F.push_back(0);
  for (int i=0; i<F.size(); i+=2) {
    ll u = (F[i]+1) * 3 + (F[i+1]+1);
    ++cnt[u];
  }
  for (int i=0; i<9; ++i) V.push_back({cnt[i], i});
  sort(V.begin(), V.end());
  if (V[0][1] > V[1][1]) swap(V[0], V[1]);
  B[V[0][1]] = B[V[1][1]] = 1;
  for (int i=0; i<9; ++i) encode_bit((ll)B[i]);
  for (int i=0; i<F.size(); i+=2) {
    ll u = (F[i]+1) * 3 + (F[i+1]+1);
    ll v = 0;
    if (u == V[0][1]) encode_bit(1), v = 6;
    else if (u == V[1][1]) encode_bit(1), v = 7;
    else {
      if (u < V[0][1]) v = u;
      else if (u < V[1][1]) v = u-1;
      else v = u-2;
    }
    for (int j=2; j>=0; --j) {
      if (v & (1LL<<j)) encode_bit(1);
      else encode_bit(0);
    }
  }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <iostream>
#include <vector>
#include <array>
#define ll long long

using namespace std;

vector <array<ll, 2>> e, adj2[1000];
vector <ll> U, X;
ll n, dist2[1000], W[1000];

void dfs(ll u, ll p) {
  for (auto [v, w] : adj2[u]) {
    if (v == p) continue;
    if (dist2[v] == (ll)1e18) {
      dist2[v] = dist2[u]+w;
      dfs(v, u);
    }
  }
}
void solve(ll u) {
  for (int i=0; i<1000; ++i) adj2[i].clear(), dist2[i] = (ll)1e18;
  dist2[u] = 0;
  for (int i=0; i<e.size(); ++i) {
    adj2[e[i][0]].push_back({e[i][1], -W[i]});
    adj2[e[i][1]].push_back({e[i][0], W[i]});
  }
  dfs(u, -1);
  for (int i=0; i<n; ++i) {
    hops(u, i, dist2[i]);
  }
}
void b3(ll u) {
  X.push_back((ll)(u/3)-1);
  X.push_back((ll)(u%3)-1);
}
void decode(int nv, int nh) {
  n = nv;
  for (ll i=1; i<nv; ++i) {
    W[i-1] = -1;
    ll u = 0;
    for (int j=0; j<10; ++j) {
      u += decode_bit() * (1LL<<j);
    }
    e.push_back({u, i});
  }
  solve(0);
  if (nh == 0) return;
  for (int i=0; i<9; ++i) {
    if (decode_bit() == 1) U.push_back(i);
  }
  for (int i=0; i<(nh-1)*(nv-1); i+=2) {
    ll a = decode_bit(), b = decode_bit(), c = decode_bit();
    if (a == 1 && b == 1 && c == 1) {
      c = decode_bit();
      if (!c) b3(U[0]);
      else b3(U[1]);
    }
    else {
      ll u = a*4+b*2+c;
      if (u >= U[0]) ++u;
      if (u >= U[1]) ++u;
      b3(u);
    }
  }
  int k = 0;
  for (int i=1; i<nh; ++i) {
    for (int j=0; j<nv-1; ++j) {
      W[j] = X[k++];
    }
    solve(i);
  }
}

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