Submission #1276284

#	Time	Username	Problem	Language	Result	Execution time	Memory
1276284		Aviansh	Saveit (IOI10_saveit)	C++20	100 / 100	48 ms	5696 KiB

encoder

#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>

using namespace std;

int n;

const int grpsiz = 3;
int grpbits = ceil(log2(((int)pow(3,grpsiz))));

void writeInt(int x, int bits){
    for(int i = 0;i<bits;i++){
        if((1<<i)&x)
            encode_bit(1);
        else
            encode_bit(0);
    }
}

void bfsupdate(int x, vector<int>g[], int par[], int dist[]){
    bool vis[n];
    fill(vis,vis+n,0);
    queue<int>q;
    q.push(x);
    dist[x]=0;
    vis[x]=1;
    while(!q.empty()){
        int nx = q.front();
        q.pop();
        for(int i : g[nx]){
            if(vis[i])
                continue;
            vis[i]=1;
            par[i]=nx;
            q.push(i);
            dist[i]=dist[nx]+1;
        }
    }
}

void bfs(int x, vector<int>g[], int dist[]){
    bool vis[n];
    fill(vis,vis+n,0);
    queue<int>q;
    q.push(x);
    dist[x]=0;
    vis[x]=1;
    while(!q.empty()){
        int nx = q.front();
        q.pop();
        for(int i : g[nx]){
            if(vis[i])
                continue;
            vis[i]=1;
            q.push(i);
            dist[i]=dist[nx]+1;
        }
    }
}

int encodeGroup(vector<int>grp){
    int ans = 0;
    for(int i = 0;i<grpsiz;i++){
        ans+=((int)pow(3,i))*(grp[i]+1);
    }
    return ans;
}

void encode(int nv, int nh, int ne, int *v1, int *v2){
    n=nv;
    vector<int>g[n];
    for(int i = 0;i<ne;i++){
        g[v1[i]].push_back(v2[i]);
        g[v2[i]].push_back(v1[i]);
    }
    int par[n];
    int dist[n];
    bfsupdate(0,g,par,dist);
    for(int i = 1;i<n;i++){
        writeInt(par[i],10);
    }
    //parent arr sent
    for(int h = 1;h<nh;h++){
        bfs(h,g,dist);
        for(int i = 1;i<n;i+=grpsiz){
            vector<int>group(grpsiz);
            for(int j = 0;j<grpsiz&&(i+j)<n;j++){
                group[j]=dist[i+j]-dist[par[i+j]];
                assert(abs(group[j])<=1);
            }
            writeInt(encodeGroup(group),grpbits);
        }
    }
}

decoder

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>

using namespace std;

int n2;

const int grpsiz2 = 3;
int grpbits2 = ceil(log2(((int)pow(3,grpsiz2))));

int readInt(int bits){
    int ans = 0;
    for(int i = 0;i<bits;i++){
        if(decode_bit()){
            ans+=(1<<i);
        }
    }
    return ans;
}

vector<int> decodeGroup(int x){
    vector<int>grp(grpsiz2);
    int ind = 0;
    while(x){
        grp[ind++]=(x%3)-1;
        x/=3;
    }
    while(ind<grpsiz2){
        grp[ind++]=-1;
    }
    return grp;
}

void dfs(int st, vector<array<int,2>>g[], int dist[], int p, int d, int par[]){
    par[st]=p;
    dist[st]=d;
    for(array<int,2>e:g[st]){
        if(e[0]==p)
            continue;
        dfs(e[0],g,dist,st,d+e[1],par);
    }
}

void decode(int nv, int nh) {
    n2=nv;
    vector<array<int,2>>g[n2];
    for(int i = 1;i<n2;i++){
        int p = readInt(10);
        g[i].push_back({p,1});
        g[p].push_back({i,1});
    }
    int dist[n2];
    int par[n2];
    dfs(0,g,dist,-1,0, par);
    for(int i = 0;i<n2;i++){
        hops(0,i,dist[i]);
    }
    int temp[n2];
    for(int h = 1;h<nh;h++){
        for(int i = 0;i<n2;i++){
            g[i].clear();
        }
        for(int i = 1;i<n2;i+=grpsiz2){
            vector<int>grp = decodeGroup(readInt(grpbits2));
            for(int j = 0;j<grpsiz2&&(i+j)<n2;j++){
                g[i+j].push_back({par[i+j],-grp[j]});
                g[par[i+j]].push_back({i+j,grp[j]});
            }
        }
        dfs(h,g,dist,-1,0,temp);
        for(int i = 0;i<n2;i++){
            hops(h,i,dist[i]);
        }
    }
}

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