Submission #796930

#	Time	Username	Problem	Language	Result	Execution time	Memory
796930		I_Love_EliskaM_	Saveit (IOI10_saveit)	C++14	0 / 100	214 ms	10284 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[i]==d[par[i]]+1) {
                   x+=t;
                } else if (d[i]==d[par[i]]-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) 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: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25