Submission #1228398

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228398		Trumling	Saveit (IOI10_saveit)	C++20	0 / 100	837 ms	16664 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;
vector<ll>par;
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>());
  par.assign(n,-1);
  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)
              {
                par[x]=curr;
                tree[curr].pb(x);
              }
              

              q.push(x);
              dist[i][x]=dist[i][curr]+1;
              vis[x]=1;
            }
      }
    }
  

  for(int i=1;i<n;i++)
    {
      ll temp=par[i];
      for(int j=0;j<10;j++)
        {
          encode_bit(temp%2);
          temp/=2;
        }
    }
    
  for(int i=0;i<n;i++)
    sort(all(tree[i]));

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

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

          if(dist[i][curr] > dist[i][x])
            {
              encode_bit(1);
              encode_bit(0);
            }
          q.push(x); 
        }
    }
  }
  assert(count<81000);
  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,0);

   for(int i=1;i<n;i++)
   {
      for(int j=0;j<10;j++)
         if(decode_bit())
            par[i]+=(1<<j);
      
      tree[par[i]].pb(i);
   }

   for(int i=0;i<n;i++)
    sort(all(tree[i]));
    
   queue<ll>q;
   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])
               {
                  bool bit=decode_bit();
                  if(!bit)
                  {
                        p[curr][x]=0;
                        p[x][curr]=0;
                  }
                  else
                  {
                     ll id=2*x + decode_bit();
                     if(id==2)
                        {
                           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: 0 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25