oj.uz

답안 #74082

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
74082 2018-08-30T03:40:12 Z imeimi2000 저장 (Saveit) (IOI10_saveit) C++17
100 / 100
 371 ms 12000 KB 
#include "grader.h"
#include "encoder.h"
#include <vector>
#include <queue>

using namespace std;

static int n;
static const int inf = 1e5;
static int dist[36][1000];
static int pr[36][1000];
static vector<int> edge[1000];

void bfs(int dist[], int pr[], int s) {
    for (int i = 0; i < n; ++i) dist[i] = inf;
    dist[s] = 0;
    queue<int> q;
    q.push(s);
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i : edge[x]) {
            if (dist[i] < inf) continue;
            dist[i] = dist[x] + 1;
            pr[i] = x;
            q.push(i);
        }
    }
}

struct encoder {
    unsigned int x, c;
    encoder() : x(0), c(0) {}
    void encode_num(int i) {
        if (c == 20) {
            for (int i = 32; i--; ) encode_bit((x >> i) & 1u);
            x = c = 0;
        }
        x = 3u * x + (unsigned int)i, ++c;
    }
    void flush() {
        while (c != 1) encode_num(0);
    }
};

void encode(int N, int H, int M, int * A, int * B) {
    n = N;
    for (int i = 0; i < M; ++i) {
        edge[A[i]].push_back(B[i]);
        edge[B[i]].push_back(A[i]);
    }
    for (int i = 0; i < H; ++i) bfs(dist[i], pr[i], i);
    for (int i = 1; i < N; ++i) {
        for (int j = 10; j--; ) {
            encode_bit((pr[0][i] >> j) & 1);
        }
    }
    encoder en;
    for (int i = 1; i < H; ++i) {
        for (int j = 1; j < N; ++j) {
            int x = dist[i][j] - dist[i][pr[0][j]] + 1;
            en.encode_num(x);
        }
    }
    en.flush();
}

#include "grader.h"
#include "decoder.h"
#include <vector>

using namespace std;

static int d[1000];
static int dist[1000];
static vector<int> edge[1000];

void dfs(int x) {
    for (int i : edge[x]) dist[i] = dist[x] + d[i], dfs(i);
}

struct decoder {
    int x[20], c;
    decoder() : c(20) {}
    int decode_num() {
        if (c < 20) return x[c++];
        else {
            unsigned int p = 0;
            for (int i = 0; i < 32; ++i) p = (p << 1u | (unsigned int)decode_bit());
            for (int i = 20; i--; p /= 3u) x[i] = p % 3u;
            c = 0;
            return x[c++];
        }
    }
};

void decode(int N, int H) {
    for (int i = 1; i < N; ++i) {
        int x = 0;
        for (int j = 0; j < 10; ++j) {
            x <<= 1;
            x ^= decode_bit();
        }
        d[i] = 1;
        edge[x].push_back(i);
    }
    dist[0] = 0;
    dfs(0);
    for (int i = 0; i < N; ++i) hops(0, i, dist[i]);
    
    decoder dc;
    for (int i = 1; i < H; ++i) {
        for (int j = 1; j < N; ++j)
            d[j] = dc.decode_num() - 1;
        dfs(0);
        for (int j = 0; j < N; ++j) hops(i, j, dist[j] - dist[i]);
    }
}

Subtask #1
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 12000 KB Output is correct - 65958 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is correct - 59358 call(s) of encode_bit()
4 Correct 7 ms 4816 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 30 ms 5948 KB Output is correct - 59358 call(s) of encode_bit()
6 Correct 38 ms 5804 KB Output is correct - 65958 call(s) of encode_bit()
7 Correct 55 ms 6232 KB Output is correct - 65958 call(s) of encode_bit()
8 Correct 27 ms 5740 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 28 ms 5692 KB Output is correct - 65958 call(s) of encode_bit()
10 Correct 31 ms 5860 KB Output is correct - 65958 call(s) of encode_bit()
11 Correct 40 ms 6016 KB Output is correct - 65958 call(s) of encode_bit()
12 Correct 30 ms 5664 KB Output is correct - 65958 call(s) of encode_bit()
13 Correct 59 ms 6432 KB Output is correct - 65958 call(s) of encode_bit()
14 Correct 41 ms 5724 KB Output is correct - 65958 call(s) of encode_bit()
15 Correct 33 ms 5852 KB Output is correct - 65958 call(s) of encode_bit()
16 Correct 74 ms 6320 KB Output is correct - 65958 call(s) of encode_bit()
17 Correct 67 ms 6128 KB Output is correct - 65958 call(s) of encode_bit()
18 Correct 44 ms 6512 KB Output is correct - 65958 call(s) of encode_bit()
19 Correct 54 ms 6076 KB Output is correct - 65958 call(s) of encode_bit()
20 Correct 70 ms 6824 KB Output is correct - 65958 call(s) of encode_bit()
21 Correct 97 ms 6896 KB Output is correct - 65958 call(s) of encode_bit()
22 Correct 74 ms 6380 KB Output is correct - 65958 call(s) of encode_bit()
23 Correct 100 ms 7064 KB Output is correct - 65958 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 12000 KB Output is correct - 65958 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is correct - 59358 call(s) of encode_bit()
4 Correct 7 ms 4816 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 30 ms 5948 KB Output is correct - 59358 call(s) of encode_bit()
6 Correct 38 ms 5804 KB Output is correct - 65958 call(s) of encode_bit()
7 Correct 55 ms 6232 KB Output is correct - 65958 call(s) of encode_bit()
8 Correct 27 ms 5740 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 28 ms 5692 KB Output is correct - 65958 call(s) of encode_bit()
10 Correct 31 ms 5860 KB Output is correct - 65958 call(s) of encode_bit()
11 Correct 40 ms 6016 KB Output is correct - 65958 call(s) of encode_bit()
12 Correct 30 ms 5664 KB Output is correct - 65958 call(s) of encode_bit()
13 Correct 59 ms 6432 KB Output is correct - 65958 call(s) of encode_bit()
14 Correct 41 ms 5724 KB Output is correct - 65958 call(s) of encode_bit()
15 Correct 33 ms 5852 KB Output is correct - 65958 call(s) of encode_bit()
16 Correct 74 ms 6320 KB Output is correct - 65958 call(s) of encode_bit()
17 Correct 67 ms 6128 KB Output is correct - 65958 call(s) of encode_bit()
18 Correct 44 ms 6512 KB Output is correct - 65958 call(s) of encode_bit()
19 Correct 54 ms 6076 KB Output is correct - 65958 call(s) of encode_bit()
20 Correct 70 ms 6824 KB Output is correct - 65958 call(s) of encode_bit()
21 Correct 97 ms 6896 KB Output is correct - 65958 call(s) of encode_bit()
22 Correct 74 ms 6380 KB Output is correct - 65958 call(s) of encode_bit()
23 Correct 100 ms 7064 KB Output is correct - 65958 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 12000 KB Output is correct - 65958 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is correct - 59358 call(s) of encode_bit()
4 Correct 7 ms 4816 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 30 ms 5948 KB Output is correct - 59358 call(s) of encode_bit()
6 Correct 38 ms 5804 KB Output is correct - 65958 call(s) of encode_bit()
7 Correct 55 ms 6232 KB Output is correct - 65958 call(s) of encode_bit()
8 Correct 27 ms 5740 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 28 ms 5692 KB Output is correct - 65958 call(s) of encode_bit()
10 Correct 31 ms 5860 KB Output is correct - 65958 call(s) of encode_bit()
11 Correct 40 ms 6016 KB Output is correct - 65958 call(s) of encode_bit()
12 Correct 30 ms 5664 KB Output is correct - 65958 call(s) of encode_bit()
13 Correct 59 ms 6432 KB Output is correct - 65958 call(s) of encode_bit()
14 Correct 41 ms 5724 KB Output is correct - 65958 call(s) of encode_bit()
15 Correct 33 ms 5852 KB Output is correct - 65958 call(s) of encode_bit()
16 Correct 74 ms 6320 KB Output is correct - 65958 call(s) of encode_bit()
17 Correct 67 ms 6128 KB Output is correct - 65958 call(s) of encode_bit()
18 Correct 44 ms 6512 KB Output is correct - 65958 call(s) of encode_bit()
19 Correct 54 ms 6076 KB Output is correct - 65958 call(s) of encode_bit()
20 Correct 70 ms 6824 KB Output is correct - 65958 call(s) of encode_bit()
21 Correct 97 ms 6896 KB Output is correct - 65958 call(s) of encode_bit()
22 Correct 74 ms 6380 KB Output is correct - 65958 call(s) of encode_bit()
23 Correct 100 ms 7064 KB Output is correct - 65958 call(s) of encode_bit()

Subtask #4
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 371 ms 12000 KB Output is correct - 65958 call(s) of encode_bit()
2 Correct 7 ms 4668 KB Output is correct - 72 call(s) of encode_bit()
3 Correct 27 ms 5644 KB Output is correct - 59358 call(s) of encode_bit()
4 Correct 7 ms 4816 KB Output is correct - 72 call(s) of encode_bit()
5 Correct 30 ms 5948 KB Output is correct - 59358 call(s) of encode_bit()
6 Correct 38 ms 5804 KB Output is correct - 65958 call(s) of encode_bit()
7 Correct 55 ms 6232 KB Output is correct - 65958 call(s) of encode_bit()
8 Correct 27 ms 5740 KB Output is correct - 63360 call(s) of encode_bit()
9 Correct 28 ms 5692 KB Output is correct - 65958 call(s) of encode_bit()
10 Correct 31 ms 5860 KB Output is correct - 65958 call(s) of encode_bit()
11 Correct 40 ms 6016 KB Output is correct - 65958 call(s) of encode_bit()
12 Correct 30 ms 5664 KB Output is correct - 65958 call(s) of encode_bit()
13 Correct 59 ms 6432 KB Output is correct - 65958 call(s) of encode_bit()
14 Correct 41 ms 5724 KB Output is correct - 65958 call(s) of encode_bit()
15 Correct 33 ms 5852 KB Output is correct - 65958 call(s) of encode_bit()
16 Correct 74 ms 6320 KB Output is correct - 65958 call(s) of encode_bit()
17 Correct 67 ms 6128 KB Output is correct - 65958 call(s) of encode_bit()
18 Correct 44 ms 6512 KB Output is correct - 65958 call(s) of encode_bit()
19 Correct 54 ms 6076 KB Output is correct - 65958 call(s) of encode_bit()
20 Correct 70 ms 6824 KB Output is correct - 65958 call(s) of encode_bit()
21 Correct 97 ms 6896 KB Output is correct - 65958 call(s) of encode_bit()
22 Correct 74 ms 6380 KB Output is correct - 65958 call(s) of encode_bit()
23 Correct 100 ms 7064 KB Output is correct - 65958 call(s) of encode_bit()