Submission #599168

#	Time	Username	Problem	Language	Result	Execution time	Memory
599168		Soumya1	Saveit (IOI10_saveit)	C++17	100 / 100	297 ms	10236 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1005;
vector<int> ad[mxN];
int par[mxN];
bool vis[mxN];
void dfs(int u) {
  vis[u] = true;
  for (int v : ad[u]) {
    if (vis[v]) continue;
    par[v] = u;
    dfs(v);
  }
}
vector<int> bfs(int s, int n) {
  vector<int> d(n, -1);
  queue<int> q;
  q.push(s);
  d[s] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : ad[u]) {
      if (d[v] == -1) {
        d[v] = d[u] + 1;
        q.push(v);
      }
    }
  }
  return d;
}
map<int, vector<int>> seq;
map<vector<int>, int> id;
int cur;
void gen(vector<int> v) {
  if (v.size() == 5) {
    id[v] = cur;
    seq[cur] = v;
    cur++;
    return;
  }
  for (int i = -1; i <= 1; i++) {
    v.push_back(i);
    gen(v);
    v.pop_back();
  }
}
void encode(int n, int h, int m, int *v1, int *v2){
  for (int i = 0; i < m; i++) {
    ad[v1[i]].push_back(v2[i]);
    ad[v2[i]].push_back(v1[i]);
  }
  dfs(0);
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      encode_bit((par[i] >> j) & 1);
    }
  }
  gen({});
  for (int i = 0; i < h; i++) {
    auto d = bfs(i, n);
    for (int j = 0; j < 10; j++) {
      encode_bit((d[0] >> j) & 1);
    }
    vector<int> v;
    for (int j = 1; j < n; j++) {
      int del = d[j] - d[par[j]];
      v.push_back(del);
    }
    while (v.size() % 5 != 0) v.push_back(0);
    for (int k = 0; k < v.size(); k += 5) {
      vector<int> V;
      for (int j = k; j < k + 5; j++) V.push_back(v[j]);
      int val = id[V];
      for (int j = 0; j < 8; j++) encode_bit((val >> j) & 1);
    }
  }
  return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;
const int mxN = 1010;
int p[mxN];
map<int, vector<int>> seqq;
map<vector<int>, int> idd;
int curr;
vector<int> adj[mxN];
int ans[mxN], del[mxN];
void dfs1(int u) {
  for (int v : adj[u]) {
    ans[v] = ans[u] + del[v];
    dfs1(v);
  }
}
void genn(vector<int> v) {
  if (v.size() == 5) {
    idd[v] = curr;
    seqq[curr] = v;
    curr++;
    return;
  }
  for (int i = -1; i <= 1; i++) {
    v.push_back(i);
    genn(v);
    v.pop_back();
  }
}
void decode(int n, int h) {
  for (int i = 1; i < n; i++) {
    for (int j = 0; j < 10; j++) {
      if (decode_bit()) p[i] |= (1 << j);
    }
  }
  for (int i = 1; i < n; i++) {
    adj[p[i]].push_back(i);
  }
  genn({});
  for (int i = 0; i < h; i++) {
    ans[0] = 0;
    for (int j = 0; j < 10; j++) {
      if (decode_bit()) ans[0] |= (1 << j);
    }
    int N = n - 1;
    while (N % 5 != 0) N++;
    for (int j = 0; j < N; j += 5) {
      int val = 0;
      for (int k = 0; k < 8; k++) {
        if (decode_bit()) val |= (1 << k);
      }
      auto v = seqq[val];
      for (int k = j; k < j + 5; k++) {
        if (k + 1 >= n) break;
        del[k + 1] = v[k - j];
      }
    }
    dfs1(0);
    for (int j = 0; j < n; j++) {
      hops(i, j, ans[j]);
    }
  }
}

Compilation message (stderr)

encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:73:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (int k = 0; k < v.size(); k += 5) {
      |                     ~~^~~~~~~~~~

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