Submission #371241

#	Time	Username	Problem	Language	Result	Execution time	Memory
371241		Sorting	Saveit (IOI10_saveit)	C++17	0 / 100	387 ms	11000 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;
const int INF = 1e9;

static vector<int> adj[N];
static int n, h, m, par[N], d[N];
static bool vis[N];

void encode_num(int x){
    for(int i = 9; i >= 0; --i)
        encode_bit((x >> i) & 1);
}

void encode_diff(int diff){
    if(diff == -1){
        encode_bit(0);
        encode_bit(0);
    }
    else if(!diff){
        encode_bit(0);
        encode_bit(1);
    }
    else{
        encode_bit(1);
        encode_bit(0);
    }
}

void bfs_0(int u, int p = -1){
    queue<int> q;
    q.push(u);
    vis[u] = true;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(!vis[to]){
                vis[to] = true;
                q.push(to);
                par[to] = v;
            }
    }
}

void bfs(int u){
    fill(d, d + n, INF);

    queue<int> q;
    q.push(u);
    d[u] = 0;

    while(!q.empty()){
        int v = q.front();
        q.pop();

        for(int to: adj[v])
            if(d[to] == INF){
                d[to] = d[u] + 1;
                q.push(to);
            }
    }

    /*cout << "d: ";
    for(int i = 0; i < n; ++i)
        cout << d[i] << " ";
    cout << endl;

    cout << "par: ";
    for(int i = 1; i < n; ++i)
        cout << par[i] << " ";
    cout << endl;*/

    for(int i = 1; i < n; ++i){
        encode_diff(d[i] - d[par[i]]);
    }
}

void encode(int _nv, int _nh, int _ne, int *v1, int *v2){
    n = _nv, h =_nh, m = _ne;
    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 0; i < m; ++i){
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }

    fill(vis, vis + n, false);
    bfs_0(0);
    for(int i = 1; i < n; ++i)
        encode_num(par[i]);

    for(int i = 1; i < h; ++i)
        bfs(i);
}

decoder

#include "grader.h"
#include "decoder.h"
#include <bits/stdc++.h>

using namespace std;

const int N = 1000 + 3;
const int H = 36 + 3;

static int n, h, par[N], d[N];
static vector<int> adj[N];
static bool vis[N];

int decode_diff(){
    int bit1 = decode_bit();
    int bit2 = decode_bit();
    if(bit1) return 1;
    if(bit2) return 0;
    return -1;
}

int decode_num(){
    int num = 0;
    for(int i = 9; i >= 0; --i)
        if(decode_bit())
            num += (1 << i);
    return num;
}

void dfs(int u){
    hops(0, u, d[u]);
    for(int to: adj[u]){
        if(to == par[u]) continue;
        d[to] = d[u] + 1;
        dfs(to);
    }
}

void dfs2(int hub, int u, int ans){
    hops(hub, u, ans);
    vis[u] = true;
    for(int to: adj[u])
        if(!vis[to]){
            if(to == par[u]) dfs2(hub, to, ans - d[u]);
            else dfs2(hub, to, ans + d[to]);
        }
}

void decode(int _nv, int _nh) {
    n = _nv, h = _nh;
    if(n == 1){
        hops(0, 0, 0);
        return;
    }

    for(int i = 0; i < n; ++i) adj[i].clear();
    for(int i = 1; i < n; ++i){
        par[i] = decode_num();
        adj[par[i]].push_back(i);
        adj[i].push_back(par[i]);
    }
    d[0] = 0;
    dfs(0);

    for(int i = 1; i < h; ++i){
        for(int j = 1; j < n; ++j)
            d[j] = decode_diff();
        fill(vis, vis + n, false);
        dfs2(i, i, 0);
    }
}

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