Submission #595992

#	Time	Username	Problem	Language	Result	Execution time	Memory
595992		Jarif_Rahman	Saveit (IOI10_saveit)	C++17	50 / 100	321 ms	10452 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){
        for(int i = 0; i < 10; i++){
            encode_bit(x%2);
            x/=2;
        }
    }

    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]);

    for(int i = 0; i < h; i++){
        auto dis = bfs(i);
        dec_to_bin(dis[0]);
        for(int j = 1; j < n; j++){
            if(dis[j] == dis[p[j]]) encode_bit(0), encode_bit(0);
            else if(dis[j] == dis[p[j]]+1) encode_bit(1), encode_bit(0);
            else encode_bit(0), encode_bit(1);
        }
    }
}

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<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);
        for(int j = 1; j < n; j++){
            int c = bin_to_dec(2);
            if(c == 1) diff[j] = 1;
            else if(c == 2) diff[j] = -1;
            else diff[j] = 0;
        }

        dfs(0, D, i);
    }
}

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