oj.uz

Submission #570452

# Submission time Handle Problem Language Result Execution time Memory
570452 2022-05-30T02:06:52 Z Deepesson Saveit (IOI10_saveit) C++17
100 / 100
 548 ms 14212 KB 
#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
///Encoder
#define MAX 1005

std::vector<int> con[MAX];

int origem[MAX];

void encode_bit(int b);

bool foi[MAX];
void explora(int pos,int prev){
    if(foi[pos])return;
    if(!prev)origem[0]=pos;
    origem[pos]=prev;
    foi[pos]=true;
    for(auto&x:con[pos])explora(x,pos);
}
int count=0;
void codifica(int x,int vals){
  //  std::cout<<"Hardcoded "<<x<<"\n";
    std::deque<int> dek;
    while(x){
        dek.push_front(x&1);
        x/=2;
    }
    while(dek.size()!=vals)dek.push_front(0);
    for(auto&x:dek){++count;encode_bit(x);}
}
typedef std::pair<int,int> pii;
void encode(int nv, int nh, int ne, int *v1, int *v2){
    for(int i=0;i!=ne;++i){
        con[v1[i]].push_back(v2[i]);
        con[v2[i]].push_back(v1[i]);
    }
    explora(0,-1);
    for(int i=1;i!=nv;++i){
        codifica(origem[i],10);
    }
    int dists[MAX][36]={};
    for(int i=0;i!=36;++i){
        std::queue<pii> queue;
        queue.push({i,0});
        bool foi[MAX]={};
        if(i<nh)
        while(queue.size()){
            auto __ = queue.front();
            queue.pop();
            auto pos=__.first,dist=__.second;
            if(foi[pos])continue;
            foi[pos]=true;
            dists[pos][i]=dist;
            for(auto&x:con[pos])queue.push({x,dist+1});
        }
    }
   // std::cout<<"ta\n";
    for(int i=0;i!=nv;++i){
        int base=0;
        int count=0;
        for(int j=0;j!=36;++j){
          //  std::cout<<"tek" <<i<<"\n";
            int dif = dists[i][j]-dists[origem[i]][j]+1;
            /// std::cout<<dists[i][j]<<" "<<dists[origem[i]][j]<<"!\n";
            base*=3;base+=dif;
           /// if(j<nh+3)
           /// std::cout<<"Dif "<<i<<" "<<dif<<"\n";
            ++count;
            if(count==6){
                count=0;
               /// std::cout<<"Escreveu "<<base<<"\n";
                codifica(base,10);
                base=0;
            }
        }
        assert(count==0);
        //std::cout<<"show" <<i<<" "<<base<<"\n";
       // std::cout<<"blz" <<i<<"\n";
    }
    //std::cout<<"ok\n";
}

///Decoder
#include <bits/stdc++.h>

#include "grader.h"
#include "encoder.h"
#define MAX 1005

int decode_bit();
void hops(int a, int b, int d);

int recebe(int x){
    int base=0;
    for(int i=0;i!=x;++i){
        base*=2;
        base+=decode_bit();
    }
    return base;
}

std::vector<int> conexao[MAX];
int pai[MAX];
int diferencas[MAX][40];
void calcular(int pos,int prev,int dist,int hub){
    hops(hub,pos,dist);
    for(auto&x:conexao[pos]){
        if(x==prev)continue;
        if(x==pai[pos])
            calcular(x,pos,dist-(diferencas[pos][hub]),hub);
        else{
            calcular(x,pos,dist+(diferencas[x][hub]),hub);
        }
    }
}

void decode(int N, int H){
    for(int i=1;i!=N;++i){
        int a = recebe(10);
       // std::cout<<"Lido "<<a<<"\n";
        int b = i;
        conexao[a].push_back(b);
        conexao[b].push_back(a);
        pai[b]=a;
    }

   // std::cout<<"ok\n";
    for(int i=0;i!=N;++i){
        for(int j=0;j!=6;++j){
            int base=recebe(10);
           /// std::cout<<"Leu "<<base<<"\n";
            std::deque<int> nos;
            for(int i=0;i!=6;++i){nos.push_back(base%3);///std::cout<<"Resta "<<base<<" "<<base%3<<"\n";
            base/=3;}

            std::reverse(nos.begin(),nos.end());
            for(int k=0;k!=6;++k){
                int val = nos[k];
                int pos = (j*6)+k;
                ///if(pos<H)
                 ///   std::cout<<"RDif "<<i<<" "<<val<<"\n";
                diferencas[i][pos]=val-1;
            }
        }
    }
  //  std::cout<<"ok\n";
    for(int i=0;i!=H;++i)calcular(i,-1,0,i);
}

Compilation message

encoder.cpp: In function 'void codifica(int, int)':
encoder.cpp:29:21: warning: comparison of integer expressions of different signedness: 'std::deque<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   29 |     while(dek.size()!=vals)dek.push_front(0);
      |           ~~~~~~~~~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 14212 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 3 ms 4732 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 27 ms 5808 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 43 ms 5988 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 38 ms 5980 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 71 ms 6484 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 26 ms 5828 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 33 ms 5676 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 5780 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 39 ms 5900 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 24 ms 5784 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 93 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 36 ms 5804 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 39 ms 5968 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 75 ms 6668 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 67 ms 6600 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 100 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 65 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 122 ms 7324 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 133 ms 7584 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 84 ms 6708 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 163 ms 7872 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 14212 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 3 ms 4732 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 27 ms 5808 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 43 ms 5988 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 38 ms 5980 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 71 ms 6484 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 26 ms 5828 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 33 ms 5676 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 5780 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 39 ms 5900 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 24 ms 5784 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 93 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 36 ms 5804 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 39 ms 5968 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 75 ms 6668 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 67 ms 6600 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 100 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 65 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 122 ms 7324 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 133 ms 7584 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 84 ms 6708 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 163 ms 7872 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 14212 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 3 ms 4732 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 27 ms 5808 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 43 ms 5988 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 38 ms 5980 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 71 ms 6484 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 26 ms 5828 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 33 ms 5676 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 5780 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 39 ms 5900 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 24 ms 5784 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 93 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 36 ms 5804 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 39 ms 5968 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 75 ms 6668 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 67 ms 6600 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 100 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 65 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 122 ms 7324 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 133 ms 7584 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 84 ms 6708 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 163 ms 7872 KB Output is correct - 69990 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 548 ms 14212 KB Output is correct - 69990 call(s) of encode_bit()
2 Correct 3 ms 4732 KB Output is correct - 340 call(s) of encode_bit()
3 Correct 27 ms 5808 KB Output is correct - 62990 call(s) of encode_bit()
4 Correct 3 ms 4728 KB Output is correct - 340 call(s) of encode_bit()
5 Correct 43 ms 5988 KB Output is correct - 62990 call(s) of encode_bit()
6 Correct 38 ms 5980 KB Output is correct - 69990 call(s) of encode_bit()
7 Correct 71 ms 6484 KB Output is correct - 69990 call(s) of encode_bit()
8 Correct 26 ms 5828 KB Output is correct - 67260 call(s) of encode_bit()
9 Correct 33 ms 5676 KB Output is correct - 69990 call(s) of encode_bit()
10 Correct 34 ms 5780 KB Output is correct - 69990 call(s) of encode_bit()
11 Correct 39 ms 5900 KB Output is correct - 69990 call(s) of encode_bit()
12 Correct 24 ms 5784 KB Output is correct - 69990 call(s) of encode_bit()
13 Correct 93 ms 6720 KB Output is correct - 69990 call(s) of encode_bit()
14 Correct 36 ms 5804 KB Output is correct - 69990 call(s) of encode_bit()
15 Correct 39 ms 5968 KB Output is correct - 69990 call(s) of encode_bit()
16 Correct 75 ms 6668 KB Output is correct - 69990 call(s) of encode_bit()
17 Correct 67 ms 6600 KB Output is correct - 69990 call(s) of encode_bit()
18 Correct 100 ms 6896 KB Output is correct - 69990 call(s) of encode_bit()
19 Correct 65 ms 6340 KB Output is correct - 69990 call(s) of encode_bit()
20 Correct 122 ms 7324 KB Output is correct - 69990 call(s) of encode_bit()
21 Correct 133 ms 7584 KB Output is correct - 69990 call(s) of encode_bit()
22 Correct 84 ms 6708 KB Output is correct - 69990 call(s) of encode_bit()
23 Correct 163 ms 7872 KB Output is correct - 69990 call(s) of encode_bit()