Submission #564991

#	Time	Username	Problem	Language	Result	Execution time	Memory
564991		shrimb	Saveit (IOI10_saveit)	C++17	25 / 100	252 ms	15624 KiB

encoder

#include "grader.h"
#include "encoder.h"
#include"bits/stdc++.h"
using namespace std;


void encode(int n, int h, int p, int *v1, int *v2){
    vector<pair<int,int>> adj[n + 1];
    for (int i = 0 ; i < p ; i++) {
        adj[v1[i]].emplace_back(v2[i],i);
        adj[v2[i]].emplace_back(v1[i],i);
    }
    vector<bool> ye(p);
    for (int i = 0 ; i < h ; i++) {
        int dist[n];
        for (int j = 0 ; j < n ; j++) dist[j] = INT_MAX;
        dist[i] = 0;
        queue<int> q;
        q.push(i);
        while (q.size()) {
            auto cur = q.front();
            q.pop();
            for (auto [j,k] : adj[cur]) {
                if (dist[j] > dist[cur] + 1) {
                    dist[j] = dist[cur] + 1;
                    ye[k] = 1;
                    q.push(j);
                }
            }
        }
    }
    for (int i = 0 ; i < p ; i++) {
        if (!ye[i]) continue;
        for (int k = 0 ; k < 10 ; k++) {
            encode_bit(bool(v1[i] & (1 << k)));
        }
        for (int k = 0 ; k < 10 ; k++) {
            encode_bit(bool(v2[i] & (1 << k)));
        }
    }
    for (int i = 0 ; i < 10 ; i++) encode_bit(1);
}

decoder

#include "grader.h"
#include "decoder.h"
#include "bits/stdc++.h"
using namespace std;
void decode(int n, int h) {

    auto getnum = [&]() {
        int ret = 0;
        for (int k = 0 ; k < 10 ; k++) {
            ret |= (1 << k) * decode_bit();
        }
        return ret;
    };

    vector<int> adj[n];

    while (true) {
        int a = getnum();
        if (__builtin_popcount(a) == 10) break;
        int b = getnum();
        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    for (int i = 0 ; i < h ; i++) {
        int dist[n];
        for (int j = 0 ; j < n ; j++) dist[j] = INT_MAX;
        queue<int> q;
        q.push(i);
        dist[i] = 0;
        while (q.size()) {
            auto cur = q.front();
            q.pop();
            for (int j : adj[cur]) {
                if (dist[j] > dist[cur] + 1) {
                    dist[j] = dist[cur] + 1;
                    q.push(j);
                }
            }
        }
        for (int j = 0 ; j < n ; j++) hops(i, j, dist[j]);
    }
}

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