Submission #1226891

#	Time	Username	Problem	Language	Result	Execution time	Memory
1226891		Trumling	Saveit (IOI10_saveit)	C++20	50 / 100	787 ms	16648 KiB

encoder

#include "grader.h"
#include "encoder.h"
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()

vector<vector<ll>>g;
vector<vector<ll>>dist;
vector<vector<ll>>tree;

ll n,h,m;
void encode(int nv, int nh, int ne, int *v1, int *v2){
  n=nv;
  h=nh;
  m=ne;
  ll count=0;
  g.assign(n,vector<ll>());
  dist.assign(n,vector<ll>(n,INF));
  tree.assign(n,vector<ll>());

  for(int i=0;i<m;i++)
    {
      g[v1[i]].pb(v2[i]);
      g[v2[i]].pb(v1[i]);
    }
  
  for(int i=0;i<n;i++)
    {
      vector<bool>vis(n,0);
      vis[i]=1;
      queue<ll>q;
      q.push(i);
      dist[i][i]=0;
      while(!q.empty())
      {
        ll curr=q.front();
        q.pop();

        for(auto x:g[curr])
          if(!vis[x])
            {
              if(i==0)
                tree[curr].pb(x);
              

              q.push(x);
              dist[i][x]=dist[i][curr]+1;
              vis[x]=1;
            }
      }
    }
  
  queue<ll>q;
  q.push(0);

  ll left=n-1;

  set<ll>s;
  for(int i=1;i<n;i++)
    s.insert(i);

  while(!q.empty())
  {
    ll curr=q.front();
    q.pop();

    for(auto x:tree[curr])
      {
        encode_bit(1);
        ll idx=0;
        for(auto itr=s.begin();itr!=s.end();itr++)
        {
          if(*itr==x)
            break;
          idx++;
        }
        
        ll temp=idx;

        ll l=0;
        while((1<<l)<=left)
          l++;

        left--;
        s.erase(x);
        for(int i=0;i<l;i++)
        {
          encode_bit(temp%2);
          temp/=2;
        }

        q.push(x); 
      }

      encode_bit(0);
  }

  for(int i=1;i<h;i++)
  {
    q.push(0);
    while(!q.empty())
    {
      ll curr=q.front();
      q.pop();
      for(auto x:tree[curr])
        {
          if(dist[i][curr] < dist[i][x])
            {
              encode_bit(1);
              encode_bit(1);
            }

          if(dist[i][curr] == dist[i][x])
            {
              encode_bit(0);
              encode_bit(0);
            }

          if(dist[i][curr] > dist[i][x])
            {
              encode_bit(0);
              encode_bit(1);
            }
          q.push(x); 
        }
    }
  }
  
  return;
}

decoder

#include "grader.h"
#include "decoder.h"
//Trumling ©
//Αφόδευε υψηλά και ηγνάντει 
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll;
#define pb push_back
#define F first
#define S second
#define enter cout<<'\n';
#define INF 99999999999999999
#define MOD 998244353
#define all(x) x.begin(),x.end()


vector<vector<ll>>tree;
vector<ll>par;
ll n,h;

void decode(int nv, int nh) {
   n=nv;
   h=nh;

   tree.assign(n,vector<ll>());
   par.assign(n,-1);


   queue<ll>q;
   q.push(0);
   ll left=n-1;
   set<ll>s;
   for(int i=1;i<n;i++)
      s.insert(i);
   
   while(!q.empty())
      {
         ll get=decode_bit();
         if(get==0)
            q.pop();
         else
         { 
            ll curr=0;

            ll l=0;
            while((1<<l)<=left)
               l++;

            left--;
               
            for(int j=0;j<l;j++)
               if(decode_bit())
                  curr+=(1<<j);
               
            ll idx=0;
            for(auto itr=s.begin();itr!=s.end();itr++)
            {
               if(idx==curr)
                  {
                     curr=*itr;
                     break;
                  }
               idx++;
            }
               
            tree[q.front()].pb(curr);
            par[curr]=q.front();
            q.push(curr);
            s.erase(curr);
            
         }
         
      }
   
   vector<vector<ll>>p(n,vector<ll>(n,0));
   for(int i=1;i<h;i++)
      {
         vector<ll>dist(n,0);
         q.push(0);
         while(!q.empty())
         {
            ll curr=q.front();
            q.pop();
            for(auto x:tree[curr])
               {
                  ll id=2*decode_bit() + decode_bit();
                  if(id==0)
                     {
                        p[curr][x]=0;
                        p[x][curr]=0;
                     }

                  if(id==1)
                     {
                        p[curr][x]=-1;
                        p[x][curr]=1;
                     }

                  if(id==3)
                     {
                        p[curr][x]=1;
                        p[x][curr]=-1; 
                     }
                  q.push(x);
               }
         }

         ll now=i;
         while(now!=0)
         {
            dist[par[now]]=dist[now]+p[now][par[now]];
            now=par[now];
         }

         q.push(0);
         while(!q.empty())
         {
            ll curr=q.front();
            q.pop();
            for(auto x:tree[curr])
               {
                  dist[x] = dist[curr] + p[curr][x];
                  q.push(x);
               }
         }

         for(int j=0;j<n;j++)
            hops(i,j,dist[j]);
         
      }

      queue<pair<ll,ll>>q2;
      q2.push({0,0});
      hops(0,0,0);
      while(!q2.empty())
      {
         pair<ll,ll>curr=q2.front();
         q2.pop();
         for(auto x:tree[curr.F])
         {
            q2.push({x,curr.S+1});
            hops(0,x,curr.S+1);
         }
      }
      

}

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