답안 #74068 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
74068	2018-08-30T02:32:13 Z	imeimi2000	저장 (Saveit) (IOI10_saveit)	C++17	75 / 100	329 ms	11872 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);
        }
    }
}


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);
        }
    }
    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;
            encode_bit((x >> 1) & 1);
            encode_bit(x & 1);
        }
    }
}

#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);
}

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]);
    
    for (int i = 1; i < H; ++i) {
        for (int j = 1; j < N; ++j) {
            int x = decode_bit() << 1;
            x ^= decode_bit();
            d[j] = x - 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	329 ms	11872 KB	Output is partially correct - 79920 call(s) of encode_bit()
2	Correct	7 ms	4800 KB	Output is correct - 56 call(s) of encode_bit()
3	Correct	30 ms	5764 KB	Output is partially correct - 71920 call(s) of encode_bit()
4	Correct	7 ms	4764 KB	Output is correct - 72 call(s) of encode_bit()
5	Correct	33 ms	5820 KB	Output is partially correct - 71920 call(s) of encode_bit()
6	Correct	40 ms	6116 KB	Output is partially correct - 79920 call(s) of encode_bit()
7	Correct	51 ms	6476 KB	Output is partially correct - 79920 call(s) of encode_bit()
8	Correct	30 ms	5820 KB	Output is partially correct - 76800 call(s) of encode_bit()
9	Correct	32 ms	5948 KB	Output is partially correct - 79920 call(s) of encode_bit()
10	Correct	26 ms	5900 KB	Output is partially correct - 79920 call(s) of encode_bit()
11	Correct	35 ms	5964 KB	Output is partially correct - 79920 call(s) of encode_bit()
12	Correct	31 ms	5852 KB	Output is partially correct - 79920 call(s) of encode_bit()
13	Correct	84 ms	6516 KB	Output is partially correct - 79920 call(s) of encode_bit()
14	Correct	33 ms	5844 KB	Output is partially correct - 79920 call(s) of encode_bit()
15	Correct	40 ms	5820 KB	Output is partially correct - 79920 call(s) of encode_bit()
16	Correct	70 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
17	Correct	69 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
18	Correct	92 ms	6664 KB	Output is partially correct - 79920 call(s) of encode_bit()
19	Correct	47 ms	6456 KB	Output is partially correct - 79920 call(s) of encode_bit()
20	Correct	93 ms	6916 KB	Output is partially correct - 79920 call(s) of encode_bit()
21	Correct	98 ms	7032 KB	Output is partially correct - 79920 call(s) of encode_bit()
22	Correct	79 ms	6588 KB	Output is partially correct - 79920 call(s) of encode_bit()
23	Correct	116 ms	7128 KB	Output is partially correct - 79920 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	329 ms	11872 KB	Output is partially correct - 79920 call(s) of encode_bit()
2	Correct	7 ms	4800 KB	Output is correct - 56 call(s) of encode_bit()
3	Correct	30 ms	5764 KB	Output is partially correct - 71920 call(s) of encode_bit()
4	Correct	7 ms	4764 KB	Output is correct - 72 call(s) of encode_bit()
5	Correct	33 ms	5820 KB	Output is partially correct - 71920 call(s) of encode_bit()
6	Correct	40 ms	6116 KB	Output is partially correct - 79920 call(s) of encode_bit()
7	Correct	51 ms	6476 KB	Output is partially correct - 79920 call(s) of encode_bit()
8	Correct	30 ms	5820 KB	Output is partially correct - 76800 call(s) of encode_bit()
9	Correct	32 ms	5948 KB	Output is partially correct - 79920 call(s) of encode_bit()
10	Correct	26 ms	5900 KB	Output is partially correct - 79920 call(s) of encode_bit()
11	Correct	35 ms	5964 KB	Output is partially correct - 79920 call(s) of encode_bit()
12	Correct	31 ms	5852 KB	Output is partially correct - 79920 call(s) of encode_bit()
13	Correct	84 ms	6516 KB	Output is partially correct - 79920 call(s) of encode_bit()
14	Correct	33 ms	5844 KB	Output is partially correct - 79920 call(s) of encode_bit()
15	Correct	40 ms	5820 KB	Output is partially correct - 79920 call(s) of encode_bit()
16	Correct	70 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
17	Correct	69 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
18	Correct	92 ms	6664 KB	Output is partially correct - 79920 call(s) of encode_bit()
19	Correct	47 ms	6456 KB	Output is partially correct - 79920 call(s) of encode_bit()
20	Correct	93 ms	6916 KB	Output is partially correct - 79920 call(s) of encode_bit()
21	Correct	98 ms	7032 KB	Output is partially correct - 79920 call(s) of encode_bit()
22	Correct	79 ms	6588 KB	Output is partially correct - 79920 call(s) of encode_bit()
23	Correct	116 ms	7128 KB	Output is partially correct - 79920 call(s) of encode_bit()

Subtask #3
25.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	329 ms	11872 KB	Output is partially correct - 79920 call(s) of encode_bit()
2	Correct	7 ms	4800 KB	Output is correct - 56 call(s) of encode_bit()
3	Correct	30 ms	5764 KB	Output is partially correct - 71920 call(s) of encode_bit()
4	Correct	7 ms	4764 KB	Output is correct - 72 call(s) of encode_bit()
5	Correct	33 ms	5820 KB	Output is partially correct - 71920 call(s) of encode_bit()
6	Correct	40 ms	6116 KB	Output is partially correct - 79920 call(s) of encode_bit()
7	Correct	51 ms	6476 KB	Output is partially correct - 79920 call(s) of encode_bit()
8	Correct	30 ms	5820 KB	Output is partially correct - 76800 call(s) of encode_bit()
9	Correct	32 ms	5948 KB	Output is partially correct - 79920 call(s) of encode_bit()
10	Correct	26 ms	5900 KB	Output is partially correct - 79920 call(s) of encode_bit()
11	Correct	35 ms	5964 KB	Output is partially correct - 79920 call(s) of encode_bit()
12	Correct	31 ms	5852 KB	Output is partially correct - 79920 call(s) of encode_bit()
13	Correct	84 ms	6516 KB	Output is partially correct - 79920 call(s) of encode_bit()
14	Correct	33 ms	5844 KB	Output is partially correct - 79920 call(s) of encode_bit()
15	Correct	40 ms	5820 KB	Output is partially correct - 79920 call(s) of encode_bit()
16	Correct	70 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
17	Correct	69 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
18	Correct	92 ms	6664 KB	Output is partially correct - 79920 call(s) of encode_bit()
19	Correct	47 ms	6456 KB	Output is partially correct - 79920 call(s) of encode_bit()
20	Correct	93 ms	6916 KB	Output is partially correct - 79920 call(s) of encode_bit()
21	Correct	98 ms	7032 KB	Output is partially correct - 79920 call(s) of encode_bit()
22	Correct	79 ms	6588 KB	Output is partially correct - 79920 call(s) of encode_bit()
23	Correct	116 ms	7128 KB	Output is partially correct - 79920 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

#	결과	실행 시간	메모리	Grader output
1	Correct	329 ms	11872 KB	Output is partially correct - 79920 call(s) of encode_bit()
2	Correct	7 ms	4800 KB	Output is correct - 56 call(s) of encode_bit()
3	Correct	30 ms	5764 KB	Output is partially correct - 71920 call(s) of encode_bit()
4	Correct	7 ms	4764 KB	Output is correct - 72 call(s) of encode_bit()
5	Correct	33 ms	5820 KB	Output is partially correct - 71920 call(s) of encode_bit()
6	Correct	40 ms	6116 KB	Output is partially correct - 79920 call(s) of encode_bit()
7	Correct	51 ms	6476 KB	Output is partially correct - 79920 call(s) of encode_bit()
8	Correct	30 ms	5820 KB	Output is partially correct - 76800 call(s) of encode_bit()
9	Correct	32 ms	5948 KB	Output is partially correct - 79920 call(s) of encode_bit()
10	Correct	26 ms	5900 KB	Output is partially correct - 79920 call(s) of encode_bit()
11	Correct	35 ms	5964 KB	Output is partially correct - 79920 call(s) of encode_bit()
12	Correct	31 ms	5852 KB	Output is partially correct - 79920 call(s) of encode_bit()
13	Correct	84 ms	6516 KB	Output is partially correct - 79920 call(s) of encode_bit()
14	Correct	33 ms	5844 KB	Output is partially correct - 79920 call(s) of encode_bit()
15	Correct	40 ms	5820 KB	Output is partially correct - 79920 call(s) of encode_bit()
16	Correct	70 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
17	Correct	69 ms	6332 KB	Output is partially correct - 79920 call(s) of encode_bit()
18	Correct	92 ms	6664 KB	Output is partially correct - 79920 call(s) of encode_bit()
19	Correct	47 ms	6456 KB	Output is partially correct - 79920 call(s) of encode_bit()
20	Correct	93 ms	6916 KB	Output is partially correct - 79920 call(s) of encode_bit()
21	Correct	98 ms	7032 KB	Output is partially correct - 79920 call(s) of encode_bit()
22	Correct	79 ms	6588 KB	Output is partially correct - 79920 call(s) of encode_bit()
23	Correct	116 ms	7128 KB	Output is partially correct - 79920 call(s) of encode_bit()

답안 #74068

Compilation message

Subtask #1 25.0 / 25.0

Subtask #2 25.0 / 25.0

Subtask #3 25.0 / 25.0

Subtask #4 0.0 / 25.0

Subtask #1
25.0 / 25.0

Subtask #2
25.0 / 25.0

Subtask #3
25.0 / 25.0

Subtask #4
0.0 / 25.0