oj.uz

답안 #23349

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
23349 2017-05-06T14:09:56 Z youngyojun 저장 (Saveit) (IOI10_saveit) C++11
100 / 100
 400 ms 11256 KB 
#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);
    }
}
#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.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 11256 KB Output is correct - 64320 call(s) of encode_bit()
2 Correct 5 ms 4804 KB Output is correct - 92 call(s) of encode_bit()
3 Correct 27 ms 5420 KB Output is correct - 60872 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 129 call(s) of encode_bit()
5 Correct 30 ms 5740 KB Output is correct - 57797 call(s) of encode_bit()
6 Correct 37 ms 5704 KB Output is correct - 62634 call(s) of encode_bit()
7 Correct 55 ms 5820 KB Output is correct - 52707 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is correct - 61503 call(s) of encode_bit()
9 Correct 28 ms 5428 KB Output is correct - 51098 call(s) of encode_bit()
10 Correct 26 ms 5400 KB Output is correct - 50528 call(s) of encode_bit()
11 Correct 32 ms 5468 KB Output is correct - 53726 call(s) of encode_bit()
12 Correct 26 ms 5224 KB Output is correct - 55084 call(s) of encode_bit()
13 Correct 72 ms 6064 KB Output is correct - 59495 call(s) of encode_bit()
14 Correct 30 ms 5448 KB Output is correct - 63020 call(s) of encode_bit()
15 Correct 31 ms 5564 KB Output is correct - 61987 call(s) of encode_bit()
16 Correct 70 ms 6000 KB Output is correct - 64338 call(s) of encode_bit()
17 Correct 40 ms 5820 KB Output is correct - 64233 call(s) of encode_bit()
18 Correct 76 ms 6396 KB Output is correct - 67005 call(s) of encode_bit()
19 Correct 45 ms 5744 KB Output is correct - 63189 call(s) of encode_bit()
20 Correct 64 ms 6680 KB Output is correct - 63421 call(s) of encode_bit()
21 Correct 108 ms 6668 KB Output is correct - 63884 call(s) of encode_bit()
22 Correct 64 ms 6200 KB Output is correct - 54724 call(s) of encode_bit()
23 Correct 114 ms 6824 KB Output is correct - 58007 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 11256 KB Output is correct - 64320 call(s) of encode_bit()
2 Correct 5 ms 4804 KB Output is correct - 92 call(s) of encode_bit()
3 Correct 27 ms 5420 KB Output is correct - 60872 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 129 call(s) of encode_bit()
5 Correct 30 ms 5740 KB Output is correct - 57797 call(s) of encode_bit()
6 Correct 37 ms 5704 KB Output is correct - 62634 call(s) of encode_bit()
7 Correct 55 ms 5820 KB Output is correct - 52707 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is correct - 61503 call(s) of encode_bit()
9 Correct 28 ms 5428 KB Output is correct - 51098 call(s) of encode_bit()
10 Correct 26 ms 5400 KB Output is correct - 50528 call(s) of encode_bit()
11 Correct 32 ms 5468 KB Output is correct - 53726 call(s) of encode_bit()
12 Correct 26 ms 5224 KB Output is correct - 55084 call(s) of encode_bit()
13 Correct 72 ms 6064 KB Output is correct - 59495 call(s) of encode_bit()
14 Correct 30 ms 5448 KB Output is correct - 63020 call(s) of encode_bit()
15 Correct 31 ms 5564 KB Output is correct - 61987 call(s) of encode_bit()
16 Correct 70 ms 6000 KB Output is correct - 64338 call(s) of encode_bit()
17 Correct 40 ms 5820 KB Output is correct - 64233 call(s) of encode_bit()
18 Correct 76 ms 6396 KB Output is correct - 67005 call(s) of encode_bit()
19 Correct 45 ms 5744 KB Output is correct - 63189 call(s) of encode_bit()
20 Correct 64 ms 6680 KB Output is correct - 63421 call(s) of encode_bit()
21 Correct 108 ms 6668 KB Output is correct - 63884 call(s) of encode_bit()
22 Correct 64 ms 6200 KB Output is correct - 54724 call(s) of encode_bit()
23 Correct 114 ms 6824 KB Output is correct - 58007 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 11256 KB Output is correct - 64320 call(s) of encode_bit()
2 Correct 5 ms 4804 KB Output is correct - 92 call(s) of encode_bit()
3 Correct 27 ms 5420 KB Output is correct - 60872 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 129 call(s) of encode_bit()
5 Correct 30 ms 5740 KB Output is correct - 57797 call(s) of encode_bit()
6 Correct 37 ms 5704 KB Output is correct - 62634 call(s) of encode_bit()
7 Correct 55 ms 5820 KB Output is correct - 52707 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is correct - 61503 call(s) of encode_bit()
9 Correct 28 ms 5428 KB Output is correct - 51098 call(s) of encode_bit()
10 Correct 26 ms 5400 KB Output is correct - 50528 call(s) of encode_bit()
11 Correct 32 ms 5468 KB Output is correct - 53726 call(s) of encode_bit()
12 Correct 26 ms 5224 KB Output is correct - 55084 call(s) of encode_bit()
13 Correct 72 ms 6064 KB Output is correct - 59495 call(s) of encode_bit()
14 Correct 30 ms 5448 KB Output is correct - 63020 call(s) of encode_bit()
15 Correct 31 ms 5564 KB Output is correct - 61987 call(s) of encode_bit()
16 Correct 70 ms 6000 KB Output is correct - 64338 call(s) of encode_bit()
17 Correct 40 ms 5820 KB Output is correct - 64233 call(s) of encode_bit()
18 Correct 76 ms 6396 KB Output is correct - 67005 call(s) of encode_bit()
19 Correct 45 ms 5744 KB Output is correct - 63189 call(s) of encode_bit()
20 Correct 64 ms 6680 KB Output is correct - 63421 call(s) of encode_bit()
21 Correct 108 ms 6668 KB Output is correct - 63884 call(s) of encode_bit()
22 Correct 64 ms 6200 KB Output is correct - 54724 call(s) of encode_bit()
23 Correct 114 ms 6824 KB Output is correct - 58007 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 400 ms 11256 KB Output is correct - 64320 call(s) of encode_bit()
2 Correct 5 ms 4804 KB Output is correct - 92 call(s) of encode_bit()
3 Correct 27 ms 5420 KB Output is correct - 60872 call(s) of encode_bit()
4 Correct 7 ms 4668 KB Output is correct - 129 call(s) of encode_bit()
5 Correct 30 ms 5740 KB Output is correct - 57797 call(s) of encode_bit()
6 Correct 37 ms 5704 KB Output is correct - 62634 call(s) of encode_bit()
7 Correct 55 ms 5820 KB Output is correct - 52707 call(s) of encode_bit()
8 Correct 27 ms 5568 KB Output is correct - 61503 call(s) of encode_bit()
9 Correct 28 ms 5428 KB Output is correct - 51098 call(s) of encode_bit()
10 Correct 26 ms 5400 KB Output is correct - 50528 call(s) of encode_bit()
11 Correct 32 ms 5468 KB Output is correct - 53726 call(s) of encode_bit()
12 Correct 26 ms 5224 KB Output is correct - 55084 call(s) of encode_bit()
13 Correct 72 ms 6064 KB Output is correct - 59495 call(s) of encode_bit()
14 Correct 30 ms 5448 KB Output is correct - 63020 call(s) of encode_bit()
15 Correct 31 ms 5564 KB Output is correct - 61987 call(s) of encode_bit()
16 Correct 70 ms 6000 KB Output is correct - 64338 call(s) of encode_bit()
17 Correct 40 ms 5820 KB Output is correct - 64233 call(s) of encode_bit()
18 Correct 76 ms 6396 KB Output is correct - 67005 call(s) of encode_bit()
19 Correct 45 ms 5744 KB Output is correct - 63189 call(s) of encode_bit()
20 Correct 64 ms 6680 KB Output is correct - 63421 call(s) of encode_bit()
21 Correct 108 ms 6668 KB Output is correct - 63884 call(s) of encode_bit()
22 Correct 64 ms 6200 KB Output is correct - 54724 call(s) of encode_bit()
23 Correct 114 ms 6824 KB Output is correct - 58007 call(s) of encode_bit()