oj.uz

Submission #512417

# Submission time Handle Problem Language Result Execution time Memory
512417 2022-01-16T10:48:49 Z alextodoran Saveit (IOI10_saveit) C++17
0 / 100
 224 ms 10588 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];

static int parent[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 dfs (int u) {
    for (int v : adj[u]) {
        if (parent[v] == -1) {
            parent[v] = u;
            dfs(v);
        }
    }
}
void dfs () {
    for (int u = 0; u < N; u++) {
        parent[u] = -1;
    }
    parent[0] = 0;
    dfs(0);
}

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]);
    }
    dfs();
    for (int u = 1; u < N; u++) {
        encode_int(parent[u], 10);
    }
    for (int h = 0; h < H; h++) {
        bfs(h, dist[h]);
        encode_int(dist[h][0], 10);
        for (int u = 1; u < N; u++) {
            assert(-1 <= dist[h][u] - dist[h][parent[u]] && dist[h][u] - dist[h][parent[u]] <= +1);
            encode_int(1 + (dist[h][u] - dist[h][parent[u]]), 2);
        }
    }
    for (int u = 0; u < N; u++) {
        adj[u].clear();
    }
}
/**
 ____ ____ ____ ____ ____
||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];

static int parent[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 u = 1; u < N; u++) {
        parent[u] = decode_int(10);
    }
    for (int h = 0; h < H; h++) {
        dist[h][0] = decode_int(10);
        for (int u = 1; u < N; u++) {
            dist[h][u] = dist[h][parent[u]] + (decode_int(2) - 1);
        }
    }
    for (int h = 0; h < H; h++) {
        for (int u = 0; u < N; u++) {
            hops(h, u, dist[h][u]);
        }
    }
}

Compilation message

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 10588 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 19 ms 5524 KB wrong parameter
4 Correct 3 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 23 ms 5716 KB wrong parameter
6 Incorrect 24 ms 5896 KB wrong parameter
7 Incorrect 39 ms 6256 KB wrong parameter
8 Incorrect 19 ms 5684 KB wrong parameter
9 Incorrect 20 ms 5736 KB wrong parameter
10 Incorrect 20 ms 5660 KB wrong parameter
11 Incorrect 22 ms 5904 KB wrong parameter
12 Incorrect 19 ms 5724 KB wrong parameter
13 Incorrect 45 ms 6340 KB wrong parameter
14 Incorrect 20 ms 5732 KB wrong parameter
15 Incorrect 22 ms 5784 KB wrong parameter
16 Incorrect 42 ms 6132 KB wrong parameter
17 Incorrect 37 ms 6340 KB wrong parameter
18 Incorrect 46 ms 6412 KB wrong parameter
19 Incorrect 38 ms 6080 KB wrong parameter
20 Incorrect 67 ms 7012 KB wrong parameter
21 Incorrect 81 ms 6932 KB wrong parameter
22 Incorrect 44 ms 6284 KB wrong parameter
23 Incorrect 93 ms 7140 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 10588 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 19 ms 5524 KB wrong parameter
4 Correct 3 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 23 ms 5716 KB wrong parameter
6 Incorrect 24 ms 5896 KB wrong parameter
7 Incorrect 39 ms 6256 KB wrong parameter
8 Incorrect 19 ms 5684 KB wrong parameter
9 Incorrect 20 ms 5736 KB wrong parameter
10 Incorrect 20 ms 5660 KB wrong parameter
11 Incorrect 22 ms 5904 KB wrong parameter
12 Incorrect 19 ms 5724 KB wrong parameter
13 Incorrect 45 ms 6340 KB wrong parameter
14 Incorrect 20 ms 5732 KB wrong parameter
15 Incorrect 22 ms 5784 KB wrong parameter
16 Incorrect 42 ms 6132 KB wrong parameter
17 Incorrect 37 ms 6340 KB wrong parameter
18 Incorrect 46 ms 6412 KB wrong parameter
19 Incorrect 38 ms 6080 KB wrong parameter
20 Incorrect 67 ms 7012 KB wrong parameter
21 Incorrect 81 ms 6932 KB wrong parameter
22 Incorrect 44 ms 6284 KB wrong parameter
23 Incorrect 93 ms 7140 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 10588 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 19 ms 5524 KB wrong parameter
4 Correct 3 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 23 ms 5716 KB wrong parameter
6 Incorrect 24 ms 5896 KB wrong parameter
7 Incorrect 39 ms 6256 KB wrong parameter
8 Incorrect 19 ms 5684 KB wrong parameter
9 Incorrect 20 ms 5736 KB wrong parameter
10 Incorrect 20 ms 5660 KB wrong parameter
11 Incorrect 22 ms 5904 KB wrong parameter
12 Incorrect 19 ms 5724 KB wrong parameter
13 Incorrect 45 ms 6340 KB wrong parameter
14 Incorrect 20 ms 5732 KB wrong parameter
15 Incorrect 22 ms 5784 KB wrong parameter
16 Incorrect 42 ms 6132 KB wrong parameter
17 Incorrect 37 ms 6340 KB wrong parameter
18 Incorrect 46 ms 6412 KB wrong parameter
19 Incorrect 38 ms 6080 KB wrong parameter
20 Incorrect 67 ms 7012 KB wrong parameter
21 Incorrect 81 ms 6932 KB wrong parameter
22 Incorrect 44 ms 6284 KB wrong parameter
23 Incorrect 93 ms 7140 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 224 ms 10588 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 19 ms 5524 KB wrong parameter
4 Correct 3 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 23 ms 5716 KB wrong parameter
6 Incorrect 24 ms 5896 KB wrong parameter
7 Incorrect 39 ms 6256 KB wrong parameter
8 Incorrect 19 ms 5684 KB wrong parameter
9 Incorrect 20 ms 5736 KB wrong parameter
10 Incorrect 20 ms 5660 KB wrong parameter
11 Incorrect 22 ms 5904 KB wrong parameter
12 Incorrect 19 ms 5724 KB wrong parameter
13 Incorrect 45 ms 6340 KB wrong parameter
14 Incorrect 20 ms 5732 KB wrong parameter
15 Incorrect 22 ms 5784 KB wrong parameter
16 Incorrect 42 ms 6132 KB wrong parameter
17 Incorrect 37 ms 6340 KB wrong parameter
18 Incorrect 46 ms 6412 KB wrong parameter
19 Incorrect 38 ms 6080 KB wrong parameter
20 Incorrect 67 ms 7012 KB wrong parameter
21 Incorrect 81 ms 6932 KB wrong parameter
22 Incorrect 44 ms 6284 KB wrong parameter
23 Incorrect 93 ms 7140 KB wrong parameter