Submission #596043

#	Time	Username	Problem	Language	Result	Execution time	Memory
596043		Jarif_Rahman	Saveit (IOI10_saveit)	C++17	100 / 100	315 ms	10192 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    void dec_to_bin(int x, int L){
        for(int i = 0; i < L; i++){
            encode_bit(x%2);
            x/=2;
        }
    }

    int ter_to_dec(vector<int> s){
        int rt = 0, p = 1;
        for(int i = 0; i < s.size(); i++) rt+=p*s[i], p*=3;
        return rt;
    }

    void ter_to_bin(vector<int> s){
        dec_to_bin(ter_to_dec(s), 8);
    }

    int n;
    vector<vector<int>> v;
    vector<bool> bl;
    vector<int> p;

    void dfs(int nd, int ss){
        if(bl[nd]) return;
        bl[nd] = 1;
        for(int x: v[nd]) if(x != ss) dfs(x, nd);
        p[nd] = ss;
    }

    vector<int> bfs(int s){
        vector<int> dis(n, -1);
        queue<int> Q;

        dis[s] = 0;
        Q.push(s);

        while(!Q.empty()){
            int nd = Q.front(); Q.pop();
            for(int x: v[nd]) if(dis[x] == -1){
                dis[x] = dis[nd]+1;
                Q.push(x);
            }
        }

        return dis;
    }
}

void encode(int _n, int h, int m, int *A, int *B){
    n = _n;
    v.assign(n, {});
    bl.assign(n, 0);
    p.assign(n, -1);

    for(int i = 0; i < m; i++){
        v[A[i]].pb(B[i]);
        v[B[i]].pb(A[i]);
    }

    dfs(0, -1);

    for(int i = 1; i < n; i++) dec_to_bin(p[i], 10);

    for(int i = 0; i < h; i++){
        auto dis = bfs(i);
        dec_to_bin(dis[0], 10);
        vector<int> s;
        for(int j = 1; j < n; j++){
            if(dis[j] == dis[p[j]]) s.pb(0);
            else if(dis[j] == dis[p[j]]+1) s.pb(1);
            else s.pb(2);
            if(s.size() == 5) ter_to_bin(s), s.clear();
        }
        if(!s.empty()) ter_to_bin(s);
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

namespace {
    int bin_to_dec(int L){
        int x = 0;
        for(int i = 0; i < L; i++) x+=decode_bit()*(1<<i);
        return x;
    }

    vector<int> bin_to_ter(){
        int x = bin_to_dec(8);
        vector<int> rt;
        for(int i = 0; i < 5; i++) rt.pb(x%3), x/=3;
        return rt;
    }

    vector<vector<int>> v;
    vector<int> p;
    vector<int> diff;

    void dfs(int nd, int d, int H){
        d+=diff[nd];
        hops(H, nd, d);
        for(int x: v[nd]) dfs(x, d, H);
    }
}

void decode(int n, int h){
    v.assign(n, {});
    p.assign(n, -1);

    for(int i = 1; i < n; i++){
        p[i] = bin_to_dec(10);
        v[p[i]].pb(i);
    }

    for(int i = 0; i < h; i++){
        int D = bin_to_dec(10);

        diff.assign(n, 0);
        vector<int> s;
        for(int j = 1; j < n; j++){
            if(s.empty()){
                s = bin_to_ter();
                reverse(s.begin(), s.end());
            }
            if(s.back() == 1) diff[j] = 1;
            else if(s.back() == 2) diff[j] = -1;
            else diff[j] = 0;

            s.pop_back();
        }

        dfs(0, D, i);
    }
}

Compilation message (stderr)

encoder.cpp: In function 'int {anonymous}::ter_to_dec(std::vector<int>)':
encoder.cpp:21:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   21 |         for(int i = 0; i < s.size(); i++) rt+=p*s[i], p*=3;
      |                        ~~^~~~~~~~~~

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