Submission #1013098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1013098		huutuan	Saveit (IOI10_saveit)	C++14	100 / 100	143 ms	13892 KiB

encoder

#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace encoder{
   const int N=1000, H=36;
   int n, h, e, dist[N][H];
   vector<int> g[N];
   int par[N];
   void send(string s){
      for (char c:s) encode_bit(c-'0');
   }
   void bfs(int root){
      queue<int> q;
      q.push(root); dist[root][root]=0;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]) if (dist[v][root]==-1){
            dist[v][root]=dist[u][root]+1;
            q.push(v);
         }
      }
   }
   void bfs2(){
      queue<int> q;
      q.push(0);
      memset(par, -1, sizeof par);
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]) if (par[v]==-1){
            par[v]=u; q.push(v);
         }
      }
   }
   void solve(int32_t _n, int32_t _h, int32_t _e, int32_t *v1, int32_t *v2){
      n=_n, h=_h, e=_e;
      for (int i=0; i<e; ++i) g[v1[i]].push_back(v2[i]), g[v2[i]].push_back(v1[i]);
      memset(dist, -1, sizeof dist);
      for (int i=0; i<h; ++i) bfs(i);
      bfs2();
      for (int i=0; i<h; ++i){
         send(bitset<10>(dist[0][i]).to_string());
      }
      for (int i=1; i<n; ++i){
         send(bitset<10>(par[i]).to_string());
         int val=0;
         for (int j=0, pw=1; j<h; ++j, pw*=3){
            int d=dist[i][j]-dist[par[i]][j]+1;
            val+=d*pw;
         }
         send(bitset<58>(val).to_string());
      }
   }
}

void encode(int32_t nv, int32_t nh, int32_t ne, int32_t *v1, int32_t *v2){
   encoder::solve(nv, nh, ne, v1, v2);
   return;
}

decoder

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>

using namespace std;

#define int long long

namespace decoder{
   const int N=1000, H=36;
   int n, h, dist[N][H], val[N], par[N];
   vector<int> g[N];
   string read(int len){
      string s;
      for (int i=0; i<len; ++i) s.push_back('0'+decode_bit());
      return s;
   }
   int vis[N];
   vector<int> bfs(){
      queue<int> q;
      q.push(0); vis[0]=1;
      vector<int> order;
      while (q.size()){
         int u=q.front(); q.pop();
         for (int v:g[u]) if (!vis[v]){
            vis[v]=1;
            q.push(v);
            order.push_back(v);
         }
      }
      return order;
   }
   void solve(int32_t _n, int32_t _h){
      n=_n, h=_h;
      for (int i=0; i<h; ++i) dist[0][i]=bitset<10>(read(10)).to_ullong();
      par[0]=-1;
      for (int i=1; i<n; ++i){
         par[i]=bitset<10>(read(10)).to_ullong();
         val[i]=bitset<58>(read(58)).to_ullong();
         g[par[i]].push_back(i);
      }
      auto order=bfs();
      for (int i:order){
         int p=par[i];
         for (int j=0; j<h; ++j){
            dist[i][j]=dist[p][j]+(val[i]%3)-1;
            val[i]/=3;
         }
      }
      for (int i=0; i<h; ++i) for (int j=0; j<n; ++j) hops(i, j, dist[j][i]);
   }
}

void decode(int32_t nv, int32_t nh) {
   decoder::solve(nv, nh);
}

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