Submission #565027

#	Time	Username	Problem	Language	Result	Execution time	Memory
565027		RealSnake	저장 (Saveit) (IOI10_saveit)	C++14	50 / 100	652 ms	12280 KiB

encoder

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

void encode(int n, int h, int p, int a[], int b[]) {
    vector<int> v[n];
    for(int i = 0; i < p; i++) {
        v[a[i]].push_back(b[i]);
        v[b[i]].push_back(a[i]);
    }
    bool vis[n];
    int dd[n];
    for(int i = n - 1; i >= 0; i--) {
        for(int j = 0; j < n; j++) {
            vis[j] = 0;
            dd[j] = 1e9;
        }
        set<pair<int, int>> s;
        s.insert({0, i});
        dd[i] = 0;
        while(s.size()) {
            pair<int, int> p = *s.begin();
            s.erase(s.begin());
            int x = p.second;
            int d = p.first;
            if(vis[x])
                continue;
            vis[x] = 1;
            for(int j : v[x]) {
                if(d + 1 < dd[j]) {
                    dd[j] = d + 1;
                    vis[x] = 0;
                    s.insert({d + 1, j});
                }
            }
        }
        for(int j = min(h - 1, i); j >= 0; j--) {
            for(int bit = 0; bit < 10; bit++)
                encode_bit((dd[j] & (1 << bit)) > 0);
        }
    }
    return;
}

decoder

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

void decode(int n, int h) {
    for(int i = n - 1; i >= 0; i--) {
        for(int j = min(h - 1, i); j >= 0; j--) {
            int d = 0;
            for(int bit = 0; bit < 10; bit++) {
                if(decode_bit())
                    d += (1 << bit);
            }
            hops(j, i, d);
            if(i < h && i != j)
                hops(i, j, d);
        }
    }
    return;
}

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