Submission #595459

#	Time	Username	Problem	Language	Result	Execution time	Memory
595459		Jarif_Rahman	Saveit (IOI10_saveit)	C++17	0 / 100	212 ms	10352 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;
}

void dfs(int nd, int d, int H){
    if(d == -1){
        d = bin_to_dec(10);
    }
    else{
        int c = bin_to_dec(2);
        if(c == 1) d++;
        else if(c == 2) d--;
    }
    hops(H, nd, d);
    for(int x: v[nd]) dfs(x, d, H);
}

void decode(int n, int h){
    v.assign(n, {});
    for(int i = 1; i < n; i++)
        v[bin_to_dec(10)].pb(i);

    for(int i = 0; i < h; i++) dfs(0, -1, i);
}

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