oj.uz

Submission #512399

# Submission time Handle Problem Language Result Execution time Memory
512399 2022-01-16T10:28:57 Z alextodoran Saveit (IOI10_saveit) C++17
0 / 100
 216 ms 10484 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>

#include "grader.h"
#include "encoder.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];

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++) {
            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>

#include "grader.h"
#include "decoder.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];

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:21:18: warning: 'E' defined but not used [-Wunused-variable]
   21 | static int N, H, E;
      |                  ^

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10484 KB wrong parameter
2 Correct 3 ms 4584 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 20 ms 5548 KB wrong parameter
4 Correct 2 ms 4588 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 5732 KB wrong parameter
6 Incorrect 26 ms 5988 KB wrong parameter
7 Incorrect 46 ms 6140 KB wrong parameter
8 Incorrect 20 ms 5632 KB wrong parameter
9 Incorrect 23 ms 5748 KB wrong parameter
10 Incorrect 24 ms 5792 KB wrong parameter
11 Incorrect 32 ms 5828 KB wrong parameter
12 Incorrect 23 ms 5720 KB wrong parameter
13 Incorrect 56 ms 6344 KB wrong parameter
14 Incorrect 22 ms 5692 KB wrong parameter
15 Incorrect 19 ms 5712 KB wrong parameter
16 Incorrect 52 ms 6288 KB wrong parameter
17 Incorrect 43 ms 6292 KB wrong parameter
18 Incorrect 42 ms 6388 KB wrong parameter
19 Incorrect 29 ms 5960 KB wrong parameter
20 Incorrect 54 ms 6696 KB wrong parameter
21 Incorrect 59 ms 6800 KB wrong parameter
22 Incorrect 54 ms 6232 KB wrong parameter
23 Incorrect 90 ms 7192 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10484 KB wrong parameter
2 Correct 3 ms 4584 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 20 ms 5548 KB wrong parameter
4 Correct 2 ms 4588 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 5732 KB wrong parameter
6 Incorrect 26 ms 5988 KB wrong parameter
7 Incorrect 46 ms 6140 KB wrong parameter
8 Incorrect 20 ms 5632 KB wrong parameter
9 Incorrect 23 ms 5748 KB wrong parameter
10 Incorrect 24 ms 5792 KB wrong parameter
11 Incorrect 32 ms 5828 KB wrong parameter
12 Incorrect 23 ms 5720 KB wrong parameter
13 Incorrect 56 ms 6344 KB wrong parameter
14 Incorrect 22 ms 5692 KB wrong parameter
15 Incorrect 19 ms 5712 KB wrong parameter
16 Incorrect 52 ms 6288 KB wrong parameter
17 Incorrect 43 ms 6292 KB wrong parameter
18 Incorrect 42 ms 6388 KB wrong parameter
19 Incorrect 29 ms 5960 KB wrong parameter
20 Incorrect 54 ms 6696 KB wrong parameter
21 Incorrect 59 ms 6800 KB wrong parameter
22 Incorrect 54 ms 6232 KB wrong parameter
23 Incorrect 90 ms 7192 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10484 KB wrong parameter
2 Correct 3 ms 4584 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 20 ms 5548 KB wrong parameter
4 Correct 2 ms 4588 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 5732 KB wrong parameter
6 Incorrect 26 ms 5988 KB wrong parameter
7 Incorrect 46 ms 6140 KB wrong parameter
8 Incorrect 20 ms 5632 KB wrong parameter
9 Incorrect 23 ms 5748 KB wrong parameter
10 Incorrect 24 ms 5792 KB wrong parameter
11 Incorrect 32 ms 5828 KB wrong parameter
12 Incorrect 23 ms 5720 KB wrong parameter
13 Incorrect 56 ms 6344 KB wrong parameter
14 Incorrect 22 ms 5692 KB wrong parameter
15 Incorrect 19 ms 5712 KB wrong parameter
16 Incorrect 52 ms 6288 KB wrong parameter
17 Incorrect 43 ms 6292 KB wrong parameter
18 Incorrect 42 ms 6388 KB wrong parameter
19 Incorrect 29 ms 5960 KB wrong parameter
20 Incorrect 54 ms 6696 KB wrong parameter
21 Incorrect 59 ms 6800 KB wrong parameter
22 Incorrect 54 ms 6232 KB wrong parameter
23 Incorrect 90 ms 7192 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 216 ms 10484 KB wrong parameter
2 Correct 3 ms 4584 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 20 ms 5548 KB wrong parameter
4 Correct 2 ms 4588 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 20 ms 5732 KB wrong parameter
6 Incorrect 26 ms 5988 KB wrong parameter
7 Incorrect 46 ms 6140 KB wrong parameter
8 Incorrect 20 ms 5632 KB wrong parameter
9 Incorrect 23 ms 5748 KB wrong parameter
10 Incorrect 24 ms 5792 KB wrong parameter
11 Incorrect 32 ms 5828 KB wrong parameter
12 Incorrect 23 ms 5720 KB wrong parameter
13 Incorrect 56 ms 6344 KB wrong parameter
14 Incorrect 22 ms 5692 KB wrong parameter
15 Incorrect 19 ms 5712 KB wrong parameter
16 Incorrect 52 ms 6288 KB wrong parameter
17 Incorrect 43 ms 6292 KB wrong parameter
18 Incorrect 42 ms 6388 KB wrong parameter
19 Incorrect 29 ms 5960 KB wrong parameter
20 Incorrect 54 ms 6696 KB wrong parameter
21 Incorrect 59 ms 6800 KB wrong parameter
22 Incorrect 54 ms 6232 KB wrong parameter
23 Incorrect 90 ms 7192 KB wrong parameter