Submission #64263

#	Time	Username	Problem	Language	Result	Execution time	Memory
64263		Abelyan	Saveit (IOI10_saveit)	C++17	0 / 100	10104 ms	5444 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second

const int N=1006,H=40,P3[6]={1,3,9,27,81,243};
vector<int> g[N],graph[N];
int pars[N],pr[H][N];
bool col[N];
queue<pair<int,int> > q;
int dist[N][H];

void to_bit(int k){
    for (int i=9;i>=0;i--){
        if (k&(1<<i)){
            encode_bit(1);
        }
        else{
            encode_bit(0);
        }
    }
}

void dfs(int v,int p=-1){
    col[v]=true;
    for (int i=0;i<g[v].size();i++){
        int to=g[v][i];
        if (!col[to]) dfs(to);
    }
    pars[v-1]=p;
}

void dfshub(int v,int hub,int p=0){
    for (int i=0;i<graph[v].size();i++){
        int to=graph[v][i];
        if (to!=p)dfshub(to,hub,v);
    }
    pr[hub][v-1]=p;
}

void encode(int n, int h, int m, int *a, int *b){
    for (int i=0;i<m;i++){
        g[a[i]].push_back(b[i]);
        g[b[i]].push_back(a[i]);
    }
    dfs(1);
    for (int i=1;i<=h;i++){
        for (int j=1;j<=n;j++)col[i]=false;
        q.push({i,0});
        while(!q.empty()){
            int v=q.front().fr,len=q.front().sc;
            col[v]=true;
            dist[v][i]=len;
            for (int j=0;j<g[v].size();j++){
                int to=g[v][j];
                if (!col[to])q.push({to,len+1});
            }
        }
    }
    for (int i=1;i<n;i++){
        to_bit(pars[i]);
        graph[i+1].push_back(pars[i]);
        graph[pars[i]].push_back(i+1);
    }
    for (int i=1;i<=h;i++)dfs(i,i);
    for (int i=2;i<=n;i++){
        int ans=0;
        for (int j=1;j<=36;j++){
            ans+=P3[6-(i%6)]*(dist[i][j]-dist[pr[j][i-1]][j]+1);
            if (ans%6==0)to_bit(ans);
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
using namespace std;

#define fr first
#define sc second

const int N=1006,H=40,P3[6]={1,3,9,27,81,243};
vector<int> gr[N];
int tarb[N][H];

int to_dec(){
    int ans=0;
    for (int i=9;i>=0;i--){
        ans+=(1<<i)*decode_bit();
    }
    return ans;
}

void to_tr(int k,int arr[]){
    for (int i=5;i>=0;i--){
        arr[i]=k/P3[i];
        k%=P3[i];
    }
}

int dfsdec(int v,int ans,int hub,int par=-1){
    for (int i=0;i<gr[v].size();i++){
        int to=gr[v][i];
        if (to!=par)dfsdec(to,ans+tarb[to][hub],hub,v);
    }
    hops(hub,v,ans);
}

void decode(int n, int h) {
    for (int i=2;i<=n;i++){
        int p=to_dec();
        gr[p].push_back(i);
        gr[i].push_back(p);
    }
    for (int i=2;i<=n;i++){
        for (int j=0;j<6;i++){
            to_tr(to_dec(),tarb[i]+(j*6+1));
        }
    }
    for (int i=1;i<=h;i++){
        dfsdec(i,0,i);
    }
}

Compilation message (stderr)

encoder.cpp: In function 'void dfs(int, int)':
encoder.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<g[v].size();i++){
                  ~^~~~~~~~~~~~
encoder.cpp: In function 'void dfshub(int, int, int)':
encoder.cpp:37:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<graph[v].size();i++){
                  ~^~~~~~~~~~~~~~~~
encoder.cpp: In function 'void encode(int, int, int, int*, int*)':
encoder.cpp:57:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
             for (int j=0;j<g[v].size();j++){
                          ~^~~~~~~~~~~~

decoder.cpp: In function 'int dfsdec(int, int, int, int)':
decoder.cpp:29:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i=0;i<gr[v].size();i++){
                  ~^~~~~~~~~~~~~
decoder.cpp:34:1: warning: no return statement in function returning non-void [-Wreturn-type]
 }
 ^

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