Submission #1255768

#	Time	Username	Problem	Language	Result	Execution time	Memory
1255768		julia_08	Saveit (IOI10_saveit)	C++20	50 / 100	56 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];

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){

  for(int i=1; i<n; i++){
    if(dist[h][i] < dist[h][pai[i]]){
      encode_bit(0);
      encode_bit(1);

    } else if(dist[h][i] == dist[h][pai[i]]){
      encode_bit(0);
      encode_bit(0);

    } else{
      encode_bit(1);
      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){

  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];

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++){

    int x = 2 * decode_bit();
    x += decode_bit();

    dif[i] = 0;

    if(x == 1){
      dif[i] = -1;
    } else if(x == 2) dif[i] = 1;

  }

  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){

  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: 0 / 25
• Subtask 4: 0 / 25