Submission #336875

#	Time	Username	Problem	Language	Result	Execution time	Memory
336875		thecodingwizard	저장 (Saveit) (IOI10_saveit)	C++11	50 / 100	281 ms	10940 KiB

encoder

#include "grader.h"
#include "encoder.h"

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define pb push_back
#define inf 1000000010
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

void sendNum(int x) {
    assert(x <= 1023);
    F0R(i, 10) {
        if (x&(1<<i)) encode_bit(1);
        else encode_bit(0);
    }
}

vector<int> adj[1000];
int pa[1000];
int dist[36][1000];

void dfs(int u, int p) {
    pa[u] = p;
    for (int v : adj[u]) {
        if (pa[v] == -1) dfs(v, u);
    }
}

void sendCode(int x) {
    assert(0 <= x && x <= 2);
    if (x==0) {
        encode_bit(0);
        encode_bit(0);
    } else if (x == 1) {
        encode_bit(0);
        encode_bit(1);
    } else {
        encode_bit(1);
        encode_bit(0);
    }
}

void encode(int n, int h, int e, int *v1, int *v2){
    F0R(i, e) {
        adj[v1[i]].pb(v2[i]);
        adj[v2[i]].pb(v1[i]);
    }
    F0R(i, n) pa[i] = -1;

    dfs(0, 0);

    FOR(i, 1, n) {
        sendNum(pa[i]);
    }

    F0R(i, 36) {
        F0R(j, n) dist[i][j] = inf;
        dist[i][i] = 0;
        queue<int> q; q.push(i);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            for (int v : adj[u]) {
                if (dist[i][v] == inf) {
                    dist[i][v] = dist[i][u]+1;
                    q.push(v);
                }
            }
        }
    }

    F0R(i, h) {
        sendNum(dist[i][0]);
        FOR(j, 1, n) {
            int p = pa[j];
            if (dist[i][j] == dist[i][p]) {
                sendCode(0);
            } else if (dist[i][j] == dist[i][p]+1) {
                sendCode(1);
            } else if (dist[i][j] == dist[i][p]-1) {
                sendCode(2);
            } else {
                cout << i << " " << j << " " << p << endl;
                cout << dist[i][j] << " " << dist[i][p] << endl;
                cerr << "??" << endl;
                exit(1);
            }
        }
    }

    return;
}

decoder

#include "grader.h"
#include "decoder.h"

#include <bits/stdc++.h>

using namespace std;

#define F0R(i, n) for (int i = 0; i < n; ++i)
#define FOR(i, a, b) for (int i = a; i < b; ++i)
#define pb push_back
#define inf 1000000010
#define ii pair<int, int>
#define f first
#define s second
#define mp make_pair

int ans[1000], codes[1000];
vector<int> children[1000];

int readNum() {
    int n = 0;
    F0R(i, 10) {
        int x = decode_bit();
        if (x) n |= (1 << i);
    }
    return n;
}

int readCode() {
    int a = decode_bit(), b = decode_bit();
    if (a == 0 && b == 0) return 0;
    if (a == 0 && b == 1) return 1;
    if (a == 1 && b == 0) return 2;
    assert(false);
}

void dfs(int u) {
    for (int v : children[u]) {
        int code = codes[v];
        if (code == 0) ans[v] = ans[u];
        else if (code == 1) ans[v] = ans[u]+1;
        else if (code == 2) ans[v] = ans[u]-1;
        else assert(false);
        dfs(v);
    }
}

void decode(int n, int h) {
    int pa[1000];

    FOR(i, 1, n) {
        pa[i] = readNum();
        children[pa[i]].pb(i);
    }
    F0R(i, h) {
        ans[0] = readNum();

        FOR(j, 1, n) {
            codes[j] = readCode();
        }

        dfs(0);

        F0R(j, n) {
            hops(i, j, ans[j]);
        }
    }
}

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