oj.uz

Submission #476894

# Submission time Handle Problem Language Result Execution time Memory
476894 2021-09-29T00:29:35 Z wiktoria_bazan Saveit (IOI10_saveit) C++14
50 / 100
 391 ms 13576 KB 
#include "grader.h"
#include "encoder.h"

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;

int const INF = 1e6 + 9;
int const N = 1e3 + 9;
int const H = 40;
int d[H][N];
bool odw[H][N];
int G[N][N];
int R[N];
string p = "";
int index = 0;
queue<int>Q;

void bfs(int v, int in) {
    Q.push(v);
    odw[in][v] = 1;
    d[in][v] = 0;
    while (!Q.empty()) {
        v = Q.front();
        Q.pop();
        for (int i = 0; i < R[v]; i++) {
            int sas = G[v][i];
            if (!odw[in][sas]) {
                odw[in][sas] = 1;
                d[in][sas] = d[in][v] + 1;
                Q.push(sas);
            }
        }
    }
}

void int_to_bits(int a) { //9 bitów
    int t = 0;
    while (a > 0) {
        encode_bit(a % 2);
        a /= 2;
        t++;
    }
    while (t < 10) {
        encode_bit(0);
        t++;
    }
}


void encode(int nv, int nh, int ne, int* v1, int* v2) {
    for (int i = 0; i < ne; i++) {
        G[v1[i]][R[v1[i]]] = v2[i];
        R[v1[i]]++;
        G[v2[i]][R[v2[i]]] = v1[i];
        R[v2[i]]++;
    }
    for (int h = 0; h < nh; h++) {
        bfs(h, h);
        for (int v = 0; v < nv; v++) {
            int_to_bits(d[h][v]);
        }
    }
    return;
}

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

void decode(int nv, int nh) {
    for (int h = 0; h < nh; h++) {
        for (int v = 0; v < nv; v++) {
            int mn = 1;
            int a = 0;
            for (int i = 0; i < 10; i++) {
                int bit = decode_bit();
                a += bit * mn;
                mn <<= 1;
            }
            hops(h, v, a);
        }
    }
}

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 13576 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4592 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 68 ms 11012 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4584 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 83 ms 10972 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 92 ms 11656 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 101 ms 11860 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 72 ms 11328 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 90 ms 11612 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11560 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 81 ms 11660 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 77 ms 11596 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 96 ms 11868 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 87 ms 11532 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 11676 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 111 ms 11836 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 102 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 118 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 84 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 140 ms 11892 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 137 ms 12160 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 106 ms 11872 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 149 ms 12092 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 391 ms 13576 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4592 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 68 ms 11012 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4584 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 83 ms 10972 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 92 ms 11656 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 101 ms 11860 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 72 ms 11328 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 90 ms 11612 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11560 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 81 ms 11660 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 77 ms 11596 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 96 ms 11868 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 87 ms 11532 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 11676 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 111 ms 11836 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 102 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 118 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 84 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 140 ms 11892 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 137 ms 12160 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 106 ms 11872 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 149 ms 12092 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 391 ms 13576 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4592 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 68 ms 11012 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4584 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 83 ms 10972 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 92 ms 11656 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 101 ms 11860 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 72 ms 11328 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 90 ms 11612 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11560 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 81 ms 11660 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 77 ms 11596 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 96 ms 11868 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 87 ms 11532 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 11676 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 111 ms 11836 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 102 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 118 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 84 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 140 ms 11892 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 137 ms 12160 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 106 ms 11872 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 149 ms 12092 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 391 ms 13576 KB Output is partially correct - 360000 call(s) of encode_bit()
2 Correct 3 ms 4592 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 68 ms 11012 KB Output is partially correct - 324000 call(s) of encode_bit()
4 Correct 2 ms 4584 KB Output is correct - 250 call(s) of encode_bit()
5 Correct 83 ms 10972 KB Output is partially correct - 324000 call(s) of encode_bit()
6 Correct 92 ms 11656 KB Output is partially correct - 360000 call(s) of encode_bit()
7 Correct 101 ms 11860 KB Output is partially correct - 360000 call(s) of encode_bit()
8 Correct 72 ms 11328 KB Output is partially correct - 345960 call(s) of encode_bit()
9 Correct 90 ms 11612 KB Output is partially correct - 360000 call(s) of encode_bit()
10 Correct 86 ms 11560 KB Output is partially correct - 360000 call(s) of encode_bit()
11 Correct 81 ms 11660 KB Output is partially correct - 360000 call(s) of encode_bit()
12 Correct 77 ms 11596 KB Output is partially correct - 360000 call(s) of encode_bit()
13 Correct 96 ms 11868 KB Output is partially correct - 360000 call(s) of encode_bit()
14 Correct 87 ms 11532 KB Output is partially correct - 360000 call(s) of encode_bit()
15 Correct 72 ms 11676 KB Output is partially correct - 360000 call(s) of encode_bit()
16 Correct 111 ms 11836 KB Output is partially correct - 360000 call(s) of encode_bit()
17 Correct 102 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
18 Correct 118 ms 11848 KB Output is partially correct - 360000 call(s) of encode_bit()
19 Correct 84 ms 11776 KB Output is partially correct - 360000 call(s) of encode_bit()
20 Correct 140 ms 11892 KB Output is partially correct - 360000 call(s) of encode_bit()
21 Correct 137 ms 12160 KB Output is partially correct - 360000 call(s) of encode_bit()
22 Correct 106 ms 11872 KB Output is partially correct - 360000 call(s) of encode_bit()
23 Correct 149 ms 12092 KB Output is partially correct - 360000 call(s) of encode_bit()