Submission #1255820

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255820		julia_08	Saveit (IOI10_saveit)	C++20	100 / 100	52 ms	6208 KiB

encoder

#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"

using namespace std;

const int MAXN = 1e3 + 10;

static int pai[MAXN];

static int dist[MAXN][MAXN], marc[MAXN][MAXN];

static vector<int> adj[MAXN];

map<string, int> ord;

void calc_ord(int pos, int &i, string &cur){

  if(pos == 5){
    ord[cur] = i++;
    return;
  }

  cur.push_back('0');
  cur.push_back('0');

  calc_ord(pos + 1, i, cur);

  cur[cur.size() - 1] = '1';
  calc_ord(pos + 1, i, cur);

  cur[cur.size() - 1] = '0';
  cur[cur.size() - 2] = '1';
  calc_ord(pos + 1, i, cur);

  cur.pop_back();
  cur.pop_back();

} 

void send_pai(int n){

  for(int i=1; i<n; i++){
    for(int j=0; j<10; j++){
      if(pai[i] & (1 << j)){
        encode_bit(1); 
      } else encode_bit(0);
    }
  }

}

void send_hub(int n, int h){

  string ans;

  for(int i=1; i<n; i++){
    if(dist[h][i] < dist[h][pai[i]]){
      ans.push_back('0');
      ans.push_back('1');

    } else if(dist[h][i] == dist[h][pai[i]]){
      ans.push_back('0');
      ans.push_back('0');

    } else{
      ans.push_back('1');
      ans.push_back('0');

    }
  }

  if((n - 1) % 5 != 0){ 
    for(int i=0; i<(5 - (n - 1) % 5); i++){
      ans.push_back('0');
      ans.push_back('0');
    }
  }

  for(int i=0; i<ans.size(); i+=10){

    string cur;

    for(int j=i; j<(i + 10); j++) cur.push_back(ans[j]);

    for(int j=0; j<8; j++){
      if(ord[cur] & (1 << j)){
        encode_bit(1);
      } else encode_bit(0);
    }

  }

}

void bfs(int h){

  queue<int> q;

  q.push(h);

  dist[h][h] = 0;
  marc[h][h] = 1;

  pai[0] = 0;

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v]){
      if(!marc[h][u]){

        dist[h][u] = dist[h][v] + 1;
        marc[h][u] = 1;
        if(h == 0) pai[u] = v;

        q.push(u);

      }
    }

  }

}

void encode(int n, int h, int p, int *a, int *b){

  int i = 0;
  string cur = "";

  calc_ord(0, i, cur);

  for(int i=0; i<n; i++) adj[i].clear();

  for(int i=0; i<h; i++){
    for(int j=0; j<n; j++){
      marc[i][j] = 0;
    }
  }

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

  for(int i=0; i<h; i++) bfs(i);

  for(int i=1; i<h; i++){
    for(int j=0; j<10; j++){
      if(dist[i][0] & (1 << j)){
        encode_bit(1);
      } else encode_bit(0);
    }
  }

  send_pai(n);

  for(int i=1; i<h; i++) send_hub(n, i);

}

decoder

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"

using namespace std;

const int MAXN = 1e3 + 10;

static int pai[MAXN];

static int dist[MAXN][MAXN], marc[MAXN][MAXN];

int dif[MAXN];

static vector<int> adj[MAXN];

map<int, string> str;

void calc_str(int pos, int &i, string &cur){

  if(pos == 5){
    str[i++] = cur;
    return;
  }

  cur.push_back('0');
  cur.push_back('0');

  calc_str(pos + 1, i, cur);

  cur[cur.size() - 1] = '1';
  calc_str(pos + 1, i, cur);

  cur[cur.size() - 1] = '0';
  cur[cur.size() - 2] = '1';
  calc_str(pos + 1, i, cur);

  cur.pop_back();
  cur.pop_back();

} 

void find_pai(int n){

  for(int i=1; i<n; i++){
    pai[i] = 0;
    for(int j=0; j<10; j++){
      pai[i] += decode_bit() * (1 << j);
    }
  }

}

void find_hub(int n, int h){

  for(int i=1; i<n; i+=5){

    int x = 0;

    for(int j=0; j<8; j++) x += decode_bit() * (1 << j);

    int j = 0, id = i;

    while(id < min(n, i + 5)){

      if(str[x][j] == '0'){

        if(str[x][j + 1] == '0'){
          dif[id] = 0;
        } else dif[id] = -1;

      } else dif[id] = 1;

      j += 2;
      id ++;

    }

  }

  queue<int> q;

  q.push(0);
  marc[h][0] = 1;

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v]){
      if(!marc[h][u]){
        marc[h][u] = 1;
        dist[h][u] = dist[h][v] + dif[u];
        q.push(u);
      }
    }

  }  

}

void decode(int n, int h){

  int i = 0;
  string cur = "";

  calc_str(0, i, cur);

  for(int i=1; i<h; i++){
    for(int j=0; j<10; j++){
      dist[i][0] += decode_bit() * (1 << j);
    }
  }

  find_pai(n);

  for(int i=0; i<h; i++){
    for(int j=0; j<n; j++){
      marc[i][j] = 0;
    }
  }

  for(int i=0; i<n; i++) adj[i].clear();

  for(int i=1; i<n; i++){
    adj[pai[i]].push_back(i);
    adj[i].push_back(pai[i]);
  }

  queue<int> q;

  for(int i=0; i<n; i++) dif[i] = 1;

  q.push(0);
  
  marc[0][0] = 1;
  dist[0][0] = 0;

  while(!q.empty()){

    int v = q.front();
    q.pop();

    for(auto u : adj[v]){
      if(!marc[0][u]){
        marc[0][u] = 1;
        dist[0][u] = dist[0][v] + dif[u];
        q.push(u);
      }
    }

  }

  for(int i=1; i<h; i++) find_hub(n, i);

  for(int i=0; i<h; i++){
    for(int j=0; j<n; j++){
      hops(i, j, dist[i][j]);
    }
  }

} 

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