Submission #598769

#	Time	Username	Problem	Language	Result	Execution time	Memory
598769		farhan132	Saveit (IOI10_saveit)	C++17	100 / 100	205 ms	10456 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 1005;
vector < ll > v[N], g[N];
ll dist[40][N];
bool vis[N]; 
ll n, h;
ll par[N];

void dfs(ll s){
  vis[s] = 1;
  for(auto u : v[s]){
    if(!vis[u]){
      g[s].pb(u);
      g[u].pb(s);
      par[u] = s;
      dfs(u);
    }
  }
  return;
}

void bfs(int source){
  for(ll i = 0; i < n; i++) dist[source][i] = -1;
  dist[source][source] = 0;
  queue < ll > q; q.push(source);
  while(q.size()){
    auto node = q.front(); q.pop();
    for(auto u : v[node]){
      if(dist[source][u] == -1){
        dist[source][u] = dist[source][node] + 1;
        q.push(u);
      }
    }
  }
  return;
}
vector < ll > mp = {-1, 0, 1};
vector < ll > cnt(3, 0);
int convert(int num){
  for(int i = 0; i < 3; i++){
    if(mp[i] == num) return i;
  }
  cout << "Something is Wrrong\n";
  return 3;
}
int start = 0;
void magic(ll s, ll p){
  for(auto u : g[s]){
    if(u - p){
      cnt[convert(dist[start][u] - dist[start][s])]++;
      magic(u, s);
    }
  }
  return;
}
void final(ll s, ll p){
  for(auto u : g[s]){
    if(u - p){
      ll k = convert(dist[start][u] - dist[start][s]);
      if(k == 0){
        encode_bit(0);
      }else{
        encode_bit(1);
        encode_bit(k - 1);
      }
      final(u, s);
    }
  }
  return;
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
  n = nv, h = nh;
  memset(vis, 0, sizeof(vis));
  for(ll i = 0; i < ne; i++){
    int x = v1[i] , y = v2[i];
    v[x].pb(y);
    v[y].pb(x);
  }
  dfs(0);
  for(ll i = 1; i < n; i++){
    for(ll j = 0; j < 10; j++){
      encode_bit((par[i] >> j)&1);
    }
  }
  for(ll i = 0; i < n; i++){
    sort(g[i].begin(), g[i].end());
  }
  for(ll i = 0; i < h; i++){
    start = i;
    bfs(i);
    magic(i, -1);
  }
  if(cnt[0] >= max(cnt[1], cnt[2])){
    encode_bit(0);
    encode_bit(0);
  }else if(cnt[1] >= max(cnt[0], cnt[2])){
    encode_bit(1);
    encode_bit(0);
    swap(mp[0], mp[1]);
  }else{
    encode_bit(0);
    encode_bit(1);
    swap(mp[0], mp[2]);
  }
  for(ll i = 0; i < h; i++){
    start = i;
    final(i, -1);
  }

  return;
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
 
using namespace std;
 
typedef int ll;
typedef pair<ll , ll> ii;
 
#define ff first
#define ss second
#define pb push_back
#define in insert

const ll N = 1005;
vector < ll > _g[N];

ll _n , _h;
vector < ll > rev = {-1, 0, 1};

void ultimate(ll s, ll p, ll D, ll source){
   hops(source, s, D);
   for(auto u : _g[s]){
      if(u - p){
         int k = decode_bit();
         if(k == 0){
            ultimate(u, s, D + rev[k], source);
         }else{
            k += decode_bit();
            ultimate(u, s, D + rev[k], source);
         }
      }
   }
   return;
}

void decode(int nv, int nh) {
   _n = nv;
   _h = nh;
   for(ll i = 1; i < _n; i++){
      ll p = 0;
      for(ll j = 0; j < 10; j++){
         int k = decode_bit();
         p |= (k << j);
      }
      _g[p].pb(i);
      _g[i].pb(p);
   }
   ll pos = 0;
   for(ll i = 0; i < 2; i++){
      int k = decode_bit();
      pos |= (k << i);
   }
   swap(rev[pos], rev[0]);
   for(ll i = 0; i < _n; i++){
      sort(_g[i].begin(), _g[i].end());
   }
   for(ll i = 0; i < _h; i++){
      ultimate(i, -1, 0, i);
   }
   return;
}

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