Submission #796934

#	Time	Username	Problem	Language	Result	Execution time	Memory
796934		I_Love_EliskaM_	Saveit (IOI10_saveit)	C++14	100 / 100	224 ms	10256 KiB

encoder

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

const int N=1e3;
vector<int> adj[N];
vector<int> nadj[N];
int par[N];

int vis[N];

void dfs(int u, int p) {
   if (vis[u]) return;
   vis[u]=1;
   par[u]=p;
   for(auto&v:adj[u]) {
      if (v==p) continue;
      dfs(v,u);
   }
}

void encode(int n, int h, int p, int a[], int b[]) {
   forn(i,p) {
      int u=a[i], v=b[i];
      adj[u].pb(v), adj[v].pb(u);
   }
   dfs(0,0);
   forn(i,n) forn(j,10) encode_bit((par[i]>>j)&1);

   vector<int> d, vis;

   forn(i,h) {
      d.assign(n,0), vis.assign(n,0);
      queue<int> q; q.push(i); vis[i]=1;
      while (q.size()) {
         auto u=q.front(); q.pop();
         for(auto&v:adj[u]) {
            if (vis[v]) continue;
            vis[v]=1;
            d[v]=d[u]+1;
            q.push(v);
         }
      }
      for (int i=0; i<n; i+=5) {
         int x=0, t=1;
         for (int j=i; j<min(i+5,n); ++j) {
            if (d[j]==d[par[j]]+1) {
               x+=t;
            } else if (d[j]==d[par[j]]-1) {
               x+=2*t;
            }
            t*=3;
         }
         forn(j,8) encode_bit((x>>j)&1);
      }
   }

}

decoder

#include "grader.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back

const int N=1e3;
vector<int> adj[N];
vector<int> nadj[N];
int par[N];

int type[N];
int d[N];

void restore(int u, int p) {
   for(auto&v:adj[u]) {
      if (v==p) continue;
      if (v==par[u]) {
         if (type[u]==0) {
            d[v]=d[u];
         } else if (type[u]==1) {
            d[v]=d[u]-1;
         } else {
            d[v]=d[u]+1;
         }
      } else {
         if (type[v]==0) {
            d[v]=d[u];
         } else if (type[v]==1) {
            d[v]=d[u]+1;
         } else {
            d[v]=d[u]-1;
         }
      }
      restore(v,u);
   }
}

void decode(int n, int h) {
   forn(i,n) adj[i].clear();
   forn(i,n) forn(j,10) par[i]|=decode_bit()<<j;
   forn(i,n) if (i) {
      adj[i].pb(par[i]);
      adj[par[i]].pb(i);
   }
   forn(u,h) {
      forn(i,n) d[i]=0;
      for(int i=0; i<n; i+=5) {
         int x=0;
         forn(j,8) x|=decode_bit()<<j;
         for (int j=i; j<min(i+5,n); ++j) {
            type[j]=x%3;
            x/=3;
         }
      }
      restore(u,-1);
      forn(i,n) hops(u,i,d[i]);
   }
}

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