oj.uz

Submission #512384

# Submission time Handle Problem Language Result Execution time Memory
512384 2022-01-16T10:16:09 Z alextodoran Saveit (IOI10_saveit) C++17
0 / 100
 258 ms 10732 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) {
    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] = N;
    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>

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 258 ms 10732 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 23 ms 5616 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 22 ms 5732 KB wrong parameter
6 Incorrect 20 ms 5796 KB wrong parameter
7 Incorrect 50 ms 6216 KB wrong parameter
8 Incorrect 19 ms 5632 KB wrong parameter
9 Incorrect 20 ms 5644 KB wrong parameter
10 Incorrect 20 ms 5612 KB wrong parameter
11 Incorrect 26 ms 5708 KB wrong parameter
12 Incorrect 20 ms 5620 KB wrong parameter
13 Incorrect 48 ms 6300 KB wrong parameter
14 Incorrect 20 ms 5596 KB wrong parameter
15 Incorrect 33 ms 5668 KB wrong parameter
16 Incorrect 57 ms 6060 KB wrong parameter
17 Incorrect 41 ms 6024 KB wrong parameter
18 Incorrect 60 ms 6472 KB wrong parameter
19 Incorrect 35 ms 5996 KB wrong parameter
20 Incorrect 75 ms 6744 KB wrong parameter
21 Incorrect 95 ms 6788 KB wrong parameter
22 Incorrect 46 ms 6228 KB wrong parameter
23 Incorrect 63 ms 6968 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 10732 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 23 ms 5616 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 22 ms 5732 KB wrong parameter
6 Incorrect 20 ms 5796 KB wrong parameter
7 Incorrect 50 ms 6216 KB wrong parameter
8 Incorrect 19 ms 5632 KB wrong parameter
9 Incorrect 20 ms 5644 KB wrong parameter
10 Incorrect 20 ms 5612 KB wrong parameter
11 Incorrect 26 ms 5708 KB wrong parameter
12 Incorrect 20 ms 5620 KB wrong parameter
13 Incorrect 48 ms 6300 KB wrong parameter
14 Incorrect 20 ms 5596 KB wrong parameter
15 Incorrect 33 ms 5668 KB wrong parameter
16 Incorrect 57 ms 6060 KB wrong parameter
17 Incorrect 41 ms 6024 KB wrong parameter
18 Incorrect 60 ms 6472 KB wrong parameter
19 Incorrect 35 ms 5996 KB wrong parameter
20 Incorrect 75 ms 6744 KB wrong parameter
21 Incorrect 95 ms 6788 KB wrong parameter
22 Incorrect 46 ms 6228 KB wrong parameter
23 Incorrect 63 ms 6968 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 10732 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 23 ms 5616 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 22 ms 5732 KB wrong parameter
6 Incorrect 20 ms 5796 KB wrong parameter
7 Incorrect 50 ms 6216 KB wrong parameter
8 Incorrect 19 ms 5632 KB wrong parameter
9 Incorrect 20 ms 5644 KB wrong parameter
10 Incorrect 20 ms 5612 KB wrong parameter
11 Incorrect 26 ms 5708 KB wrong parameter
12 Incorrect 20 ms 5620 KB wrong parameter
13 Incorrect 48 ms 6300 KB wrong parameter
14 Incorrect 20 ms 5596 KB wrong parameter
15 Incorrect 33 ms 5668 KB wrong parameter
16 Incorrect 57 ms 6060 KB wrong parameter
17 Incorrect 41 ms 6024 KB wrong parameter
18 Incorrect 60 ms 6472 KB wrong parameter
19 Incorrect 35 ms 5996 KB wrong parameter
20 Incorrect 75 ms 6744 KB wrong parameter
21 Incorrect 95 ms 6788 KB wrong parameter
22 Incorrect 46 ms 6228 KB wrong parameter
23 Incorrect 63 ms 6968 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 258 ms 10732 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 94 call(s) of encode_bit()
3 Incorrect 23 ms 5616 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 130 call(s) of encode_bit()
5 Incorrect 22 ms 5732 KB wrong parameter
6 Incorrect 20 ms 5796 KB wrong parameter
7 Incorrect 50 ms 6216 KB wrong parameter
8 Incorrect 19 ms 5632 KB wrong parameter
9 Incorrect 20 ms 5644 KB wrong parameter
10 Incorrect 20 ms 5612 KB wrong parameter
11 Incorrect 26 ms 5708 KB wrong parameter
12 Incorrect 20 ms 5620 KB wrong parameter
13 Incorrect 48 ms 6300 KB wrong parameter
14 Incorrect 20 ms 5596 KB wrong parameter
15 Incorrect 33 ms 5668 KB wrong parameter
16 Incorrect 57 ms 6060 KB wrong parameter
17 Incorrect 41 ms 6024 KB wrong parameter
18 Incorrect 60 ms 6472 KB wrong parameter
19 Incorrect 35 ms 5996 KB wrong parameter
20 Incorrect 75 ms 6744 KB wrong parameter
21 Incorrect 95 ms 6788 KB wrong parameter
22 Incorrect 46 ms 6228 KB wrong parameter
23 Incorrect 63 ms 6968 KB wrong parameter