Submission #998139

#	Time	Username	Problem	Language	Result	Execution time	Memory
998139		bachhoangxuan	Saveit (IOI10_saveit)	C++17	100 / 100	159 ms	16548 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1005;

void encode(int N, int H, int P, int *A, int *B){
    vector<vector<int>> edge(N);
    vector<int> par(N),dist(N);
    for(int i=0;i<P;i++){
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    for(int i=0;i<H;i++){
        dist.assign(N,-1);
        queue<int> q;q.push(i);dist[i]=0;
        while(!q.empty()){
            int u=q.front();q.pop();
            for(int v:edge[u]){
                if(dist[v]!=-1) continue;
                q.push(v);dist[v]=dist[u]+1;
                if(!i) par[v]=u;
            }
        }
        if(!i){
            for(int j=1;j<N;j++) for(int k=0;k<10;k++) encode_bit(par[j]>>k&1);
        }
        for(int j=1;j<N;j+=5){
            int num=0;
            for(int u=j;u<min(N,j+5);u++){
                num=num*3+dist[u]-dist[par[u]]+1;
                //cout << i << ' ' << u << ' ' << dist[u]-dist[par[u]] << '\n';
            }
            for(int k=0;k<8;k++) encode_bit(num>>k&1);
        }
    }
}

decoder

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

void decode(int N, int H) {
    vector<int> par(N),dist(N);
    vector<vector<int>> edge(N);
    vector<vector<int>> dd(H,vector<int>(N,0));
    for(int i=1;i<N;i++){
        for(int j=0;j<10;j++) par[i]+=decode_bit()<<j;
        edge[par[i]].push_back(i);
        edge[i].push_back(par[i]);
        //cout << par[i] << '\n';
    }
    for(int i=0;i<H;i++){
        //cout << '*' << i << '\n';
        for(int j=1;j<N;j+=5){
            int num=0;
            for(int k=0;k<8;k++) num+=decode_bit()<<k;
            for(int u=min(N,j+5)-1;u>=j;u--){
                dist[u]=num%3-1;num/=3;
                //cout << u << ' ' << par[u] <<  ' ' << dist[u] << '\n';
            }
        }
        function<void(int,int)> dfs = [&](int u,int p){
            for(int v:edge[u]){
                if(v==p) continue;
                int w=(par[v]==u?dist[v]:-dist[u]);
                dd[i][v]=dd[i][u]+w;dfs(v,u);
            }
        };
        dd[i][i]=0;
        dfs(i,-1);
        for(int j=0;j<N;j++){
            //cout << "hh " << i << ' ' << j << ' ' << dd[i][j] << '\n';
            hops(i,j,dd[i][j]);
        }
        //cout << '\n';
    }
}

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