Submission #45123

#	Time	Username	Problem	Language	Result	Execution time	Memory
45123		tjd229	Saveit (IOI10_saveit)	C++11	50 / 100	443 ms	15656 KiB

encoder

#include "grader.h"
#include "encoder.h"
int p[1000];
int visit[1000];
int edge[1000][1000];
int tail[1000];
void bfs(int nv,int src){
   visit[src] = src + 1;
   int i;
   int q[1000];
   int front = 0;
   int back = 0;
   q[back++] = src;
   while (front != back){
      int curr = q[front++];
      for (i = 0; i < tail[curr]; i++){
         int nxt = edge[curr][i];
         if (visit[nxt] != src + 1){
            visit[nxt] = src + 1;
            q[back++] = nxt;
            p[nxt] = curr;
         }
      }
   }
}
void encode(int nv, int nh, int ne, int *v1, int *v2){
   int i,j;
   int u, v;
   while (ne--){
      u = v1[ne];
      v = v2[ne];
      edge[u][tail[u]++] = v;
      edge[v][tail[v]++] = u;
   }
   for (i = 0; i < nh; i++){
      bfs(nv, i);
      for (j = 0; j < nv; j++){
         if (j == i) continue;
         u = p[j];
         v = 10;
         while (v--){
            encode_bit(u&1);
            u >>= 1;
         }
      }
   }

   return;
}

decoder

#include "grader.h"
#include "decoder.h"
void dfs(int src,int ix, int depth, int *tail, int edge[1000][1000]){
   hops(src, ix, depth);
   for (int i = 0; i < tail[ix]; i++)
      dfs(src,edge[ix][i],depth+1,tail,edge);
}
void decode(int nv, int nh) {
   int i, j, k;
   
   for (i = 0; i < nh; i++){
      int edge[1000][1000];
      int tail[1000] = { 0 };
      for (j = 0; j < nv; j++){
         if (i == j) continue;

         int p = 0;
         for (k = 0; k < 10;k++){
            int b = decode_bit();
            p += (b<<k);            
         }
         edge[p][tail[p]++] = j;
      }
      dfs(i,i,0,tail,edge);
      
   }
}

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