oj.uz

Submission #512410

# Submission time Handle Problem Language Result Execution time Memory
512410 2022-01-16T10:43:19 Z alextodoran Saveit (IOI10_saveit) C++17
50 / 100
 350 ms 12616 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

static const int N_MAX = 1000;
static const int H_MAX = 36;

static int N, H, E;

static int dist[H_MAX][N_MAX];

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

void encode_bit (int bit);

void encode_int (int val, int len) {
    assert(0 <= val && val < (1 << len));
    for (int bit = len - 1; bit >= 0; bit--) {
        encode_bit((val >> bit) & 1);
    }
}

static vector <int> adj[N_MAX];

void bfs (int s, int dist[]) {
    for (int u = 0; u < N; u++) {
        dist[u] = -1;
    }
    queue <int> q;
    dist[s] = 0;
    q.push(s);
    while (q.empty() == false) {
        int u = q.front();
        q.pop();
        for (int v : adj[u]) {
            if (dist[v] == -1) {
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

void encode (int nv, int nh, int ne, int *v1, int *v2) {
    N = nv; H = nh; E = ne;
    for (int i = 0; i < E; i++) {
        adj[v1[i]].push_back(v2[i]);
        adj[v2[i]].push_back(v1[i]);
    }
    for (int h = 0; h < H; h++) {
        bfs(h, dist[h]);
        for (int u = 0; u < N; u++) {
            encode_int(dist[h][u], 10);
        }
    }
}
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

static const int N_MAX = 1000;
static const int H_MAX = 36;

static int N, H, E;

static int dist[H_MAX][N_MAX];

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

int decode_bit ();

void hops (int a, int b, int d);

int decode_int (int len) {
    int val = 0;
    for (int bit = len - 1; bit >= 0; bit--) {
        val |= (decode_bit() << bit);
    }
    return val;
}

void decode (int nv, int nh) {
    N = nv; H = nh;
    for (int h = 0; h < H; h++) {
        for (int u = 0; u < N; u++) {
            hops(h, u, decode_int(10));
        }
    }
}

Compilation message

decoder.cpp:20:12: warning: 'dist' defined but not used [-Wunused-variable]
   20 | static int dist[H_MAX][N_MAX];
      |            ^~~~
decoder.cpp:18:18: warning: 'E' defined but not used [-Wunused-variable]
   18 | static int N, H, E;
      |                  ^

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 12616 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 55 ms 7676 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 1 ms 4580 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 67 ms 7580 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 73 ms 7888 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 86 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 82 ms 7644 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 66 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 63 ms 7760 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 74 ms 7936 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 71 ms 7688 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 118 ms 8380 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 79 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 7836 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 95 ms 8300 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 92 ms 8140 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 92 ms 8416 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 79 ms 8056 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 106 ms 8820 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 117 ms 8968 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 103 ms 8360 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 133 ms 9076 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #2
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 12616 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 55 ms 7676 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 1 ms 4580 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 67 ms 7580 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 73 ms 7888 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 86 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 82 ms 7644 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 66 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 63 ms 7760 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 74 ms 7936 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 71 ms 7688 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 118 ms 8380 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 79 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 7836 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 95 ms 8300 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 92 ms 8140 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 92 ms 8416 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 79 ms 8056 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 106 ms 8820 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 117 ms 8968 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 103 ms 8360 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 133 ms 9076 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 12616 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 55 ms 7676 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 1 ms 4580 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 67 ms 7580 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 73 ms 7888 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 86 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 82 ms 7644 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 66 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 63 ms 7760 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 74 ms 7936 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 71 ms 7688 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 118 ms 8380 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 79 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 7836 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 95 ms 8300 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 92 ms 8140 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 92 ms 8416 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 79 ms 8056 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 106 ms 8820 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 117 ms 8968 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 103 ms 8360 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 133 ms 9076 KB Output is partially correct - 360000 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 350 ms 12616 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 2 ms 4588 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 55 ms 7676 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 1 ms 4580 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 67 ms 7580 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 73 ms 7888 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 86 ms 8176 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 82 ms 7644 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 66 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 63 ms 7760 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 74 ms 7936 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 71 ms 7688 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 118 ms 8380 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 79 ms 7700 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 7836 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 95 ms 8300 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 92 ms 8140 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 92 ms 8416 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 79 ms 8056 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 106 ms 8820 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 117 ms 8968 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 103 ms 8360 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 133 ms 9076 KB Output is partially correct - 360000 call(s) of encode_bit()