Submission #23349

#	Time	Username	Problem	Language	Result	Execution time	Memory
23349		youngyojun	Saveit (IOI10_saveit)	C++11	100 / 100	400 ms	11256 KiB

encoder

#include "encoder.h"
#include "grader.h"
#include <vector>
#include <algorithm>
#include <queue>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
static const int huffswtd[3][3] = { {0, 1, 2}, {1, 0, 2}, {1, 2, 0} }; // [huffno][data]
static inline void fg(vector<int> G[], const int& A, const int& B) { G[A].pb(B); G[B].pb(A); }
static inline void callbit(const int& n, const int& k) {
    for(int i = k-1; ~i; i--) encode_bit((n & (1<<i)) ? 1 : 0);
}
static inline void callhuffbit(const int& huffcode) {
    if(0 == huffcode) encode_bit(1);
    else if(1 == huffcode) { encode_bit(0); encode_bit(1); }
    else { encode_bit(0); encode_bit(0); }
}

static vector<int> G[1005];
static int prt[1005], d[1005], sddt[1005];
static int cnt[3]; // -1, 0, 1
static int N, H;

static void dfs(const int& idx) {
    for(int i = 0; i < sz(G[idx]); i++) {
        if(~prt[G[idx][i]]) continue;
        prt[G[idx][i]] = idx; dfs(G[idx][i]);
    }
}
static inline void bfs(const int& ridx) {
    queue<int> Q; fill(d, d+N, -1);
    d[ridx] = 0; Q.push(ridx); while(!Q.empty()) {
        const int idx = Q.front(); Q.pop();
        for(int i = 0; i < sz(G[idx]); i++) {
            const int &nidx = G[idx][i];
            if(~d[nidx]) continue;
            d[nidx] = d[idx] + 1; Q.push(nidx);
        }
    }
}
void encode(int _N, int _H, int _P, int _A[], int _B[]) {
    N = _N; H = _H; for(int i = 0; i < _P; i++) fg(G, _A[i], _B[i]);
    fill(prt, prt+N, -1); prt[0] = 0;
    dfs(0); for(int i = 1; i < N; i++) callbit(prt[i], 10);
    for(int h = 0; h < H; h++) {
        bfs(h); callbit(d[0], 10);
        for(int i = 1; i < N; i++) sddt[i] = d[prt[i]] - d[i];
        fill(cnt, cnt+3, 0); for(int i = 1; i < N; i++) cnt[sddt[i]+1]++;
        const int maxcnt = *max_element(cnt, cnt+3);
        int huffno = -1;
        if(maxcnt == cnt[0]) huffno = 0;
        else if(maxcnt == cnt[1]) huffno = 1;
        else huffno = 2;
        for(int i = 1; i < N; i++) callhuffbit(huffswtd[huffno][sddt[i]+1]);
        callbit(huffno, 2);
    }
}

decoder

#include "grader.h"
#include "decoder.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
#define pb push_back
#define sz(V) ((int)(V).size())
#define allv(V) ((V).begin()),((V).end())
using namespace std;
static const int huffswtd[3][3] = { {0, 1, 2}, {1, 0, 2}, {2, 0, 1} };
static inline int readbit(const int& k) {
    int ret = 0;
    for(int i = 0; i < k; i++) { ret *= 2; ret += decode_bit(); }
    return ret;
}
static inline int readhuffbit() {
    if(1 == decode_bit()) return 0;
    if(1 == decode_bit()) return 1;
    return 2;
}

static vector<int> G[1005];
static vector<int> CV;
static int Gocnt[1005];
static int prt[1005], diff[1005], d[1005];
static int N, H;

static inline void graphsort() {
    vector<int> V;
    for(int i = 1; i < N; i++) G[prt[i]].pb(i);
    for(int i = 0; i < N; i++) for(int j = 0; j < sz(G[i]); j++) Gocnt[G[i][j]]++;
    for(int i = 0; i < N; i++) if(!Gocnt[i]) V.pb(i);
    while(!V.empty()) {
        const int idx = V.back(); V.pop_back(); CV.pb(idx);
        for(int i = 0; i < sz(G[idx]); i++) if(!(--Gocnt[G[idx][i]])) V.pb(G[idx][i]);
    }
}
void decode(int nv, int nh) {
    N = nv; H = nh;
    for(int i = 1; i < N; i++) prt[i] = readbit(10);
    graphsort();
    for(int h = 0; h < nh; h++) {
        d[0] = readbit(10);
        for(int i = 1; i < N; i++) diff[i] = readhuffbit();
        const int huffno = readbit(2);
        for(int i = 1; i < N; i++) diff[i] = huffswtd[huffno][diff[i]];
        for(int i = 1; i < N; i++) diff[i]--;
        for(int i = 1; i < N; i++) d[CV[i]] = d[prt[CV[i]]] - diff[CV[i]];
        for(int i = 0; i < N; i++) hops(h, i, d[i]);
    }
}

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