oj.uz

Submission #477152

# Submission time Handle Problem Language Result Execution time Memory
477152 2021-09-30T23:14:03 Z wiktoria_bazan Saveit (IOI10_saveit) C++14
0 / 100
 416 ms 9972 KB 
#include "grader.h"
#include "encoder.h"
#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

typedef long long ll;
int const N = 1e3 + 9;
int const H = 36;

vector<int> G[N];
queue<int>Q;
int warstwa[N];
int ojciec[N];
bool odw[N];
int d[N];

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

void dfs(int v, int o) {
    odw[v] = 0;
    ojciec[v] = o;
    d[v] = warstwa[v] - warstwa[o] + 1;
    sort(G[v].begin(), G[v].end());
    for (int i = 0; i < G[v].size(); i++) {
        int sas = G[v][i];
        if (odw[sas] == 1) {
            dfs(sas, v);
        }
    }
}


void ll_to_bits(ll a, int b) {
    int t = 0;
    while (a > 0) {
        encode_bit(a % 2);
        a /= 2;
        t++;
    }
    while (t < b) {
        encode_bit(0);
        t++;
    }
}

void odll(int nv) {
    ll a = 0, mn = 1;
    for (int v = 0; v < nv; v++) {
        a += mn * d[v];
        mn *= 3;
    }
    ll_to_bits(a, 58);
}

void koduj_drzewo(int nv) {
    for (int v = 0; v < nv; v++) {
        ll_to_bits(ojciec[v], 10);
    }
}

void encode(int nv, int nh, int ne, int* v1, int* v2) {
  for (int i = 0; i < ne; i++) {
      G[v1[i]].push_back(v2[i]);
      G[v2[i]].push_back(v1[i]);
  }
  bfs(0);
  dfs(0, 0);
  koduj_drzewo(nv);
  ll_to_bits(warstwa[0], 10); //koduj 0
  odll(nv);
  for (int h = 1; h < nh; h++) {
      bfs(h);
      dfs(0, 0);
      ll_to_bits(warstwa[0], 10); //koduj 0
      odll(nv);
  }
}

#include "grader.h"
#include "decoder.h"
#include <iostream>
#include <vector>
#include<algorithm>
using namespace std;

typedef long long ll;
int const N = 1e3 + 9;

int O[N];
vector<int> G[N];
int odl[N];
bool ost = true;
bool odw[N];
int d[N];

void policz(int v) {
    odw[v] = ost;
    d[v] = d[O[v]] + odl[v];
    sort(G[v].begin(), G[v].end());
    for (int i = 0; i < G[v].size(); i++) {
        int syn = G[v][i];
        if (odw[syn] != ost) {
            policz(syn);
        }
    }
}

void odzyskaj(int a) {
    int t = 0;
    while (a > 0) {
        odl[t] = (a % 3) - 1;
        a /= 3;
        t++;
    }
    while (t < 58) {
        odl[t] = -1;
        t++;
    }
}

void wypisz(int nv, int h) {
    for (int v = 0; v < nv; v++) {
        hops(h, v, d[v]);
    }
}

void fczytaj_ojcuf(int nv) {
    for (int v = 0; v < nv; v++) {
        int o = 0, mn = 1;
        for (int i = 0; i < 10; i++) {
            int bit = decode_bit();
            o += mn * bit;
            mn <<= 1;
        }
        O[v] = o;
        G[o].push_back(v);
    }
}

int fczytaj_od_od_zera() {
        int o = 0, mn = 1;
        for (int i = 0; i < 10; i++) {
            int bit = decode_bit();
            o += mn * bit;
            mn <<= 1;
        }
        return o;
}

void fczytaj_odl(int nh, int nv) {
    for (int h = 0; h < nh; h++) {
        d[0] = fczytaj_od_od_zera();
        int a = 0, mn = 1;
        for (int i = 0; i < 58; i++) {
            int bit = decode_bit();
            a += mn * bit;
            mn <<= 1;
        }
        odzyskaj(a);
        policz(0);
        ost = !ost;
        wypisz(nv, h);
    }
}

void decode(int nv, int nh) {
    fczytaj_ojcuf(nv);
    fczytaj_odl(nh, nv);
}

Compilation message

encoder.cpp: In function 'void bfs(int)':
encoder.cpp:27:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |         for (int i = 0; i < G[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
encoder.cpp: In function 'void dfs(int, int)':
encoder.cpp:43:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for (int i = 0; i < G[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

decoder.cpp: In function 'void policz(int)':
decoder.cpp:22:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 |     for (int i = 0; i < G[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 416 ms 9972 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 12 ms 5056 KB wrong parameter
4 Correct 4 ms 4588 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 18 ms 5200 KB wrong parameter
6 Incorrect 17 ms 5200 KB wrong parameter
7 Incorrect 65 ms 5412 KB wrong parameter
8 Incorrect 12 ms 4972 KB wrong parameter
9 Incorrect 13 ms 4920 KB wrong parameter
10 Incorrect 17 ms 4896 KB wrong parameter
11 Incorrect 20 ms 5076 KB wrong parameter
12 Incorrect 10 ms 4948 KB wrong parameter
13 Incorrect 72 ms 5616 KB wrong parameter
14 Incorrect 13 ms 4972 KB wrong parameter
15 Incorrect 15 ms 5028 KB wrong parameter
16 Incorrect 87 ms 5412 KB wrong parameter
17 Incorrect 50 ms 5348 KB wrong parameter
18 Incorrect 93 ms 5640 KB wrong parameter
19 Incorrect 33 ms 5364 KB wrong parameter
20 Incorrect 138 ms 6068 KB wrong parameter
21 Incorrect 129 ms 6144 KB wrong parameter
22 Incorrect 56 ms 5684 KB wrong parameter
23 Incorrect 138 ms 6340 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 416 ms 9972 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 12 ms 5056 KB wrong parameter
4 Correct 4 ms 4588 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 18 ms 5200 KB wrong parameter
6 Incorrect 17 ms 5200 KB wrong parameter
7 Incorrect 65 ms 5412 KB wrong parameter
8 Incorrect 12 ms 4972 KB wrong parameter
9 Incorrect 13 ms 4920 KB wrong parameter
10 Incorrect 17 ms 4896 KB wrong parameter
11 Incorrect 20 ms 5076 KB wrong parameter
12 Incorrect 10 ms 4948 KB wrong parameter
13 Incorrect 72 ms 5616 KB wrong parameter
14 Incorrect 13 ms 4972 KB wrong parameter
15 Incorrect 15 ms 5028 KB wrong parameter
16 Incorrect 87 ms 5412 KB wrong parameter
17 Incorrect 50 ms 5348 KB wrong parameter
18 Incorrect 93 ms 5640 KB wrong parameter
19 Incorrect 33 ms 5364 KB wrong parameter
20 Incorrect 138 ms 6068 KB wrong parameter
21 Incorrect 129 ms 6144 KB wrong parameter
22 Incorrect 56 ms 5684 KB wrong parameter
23 Incorrect 138 ms 6340 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 416 ms 9972 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 12 ms 5056 KB wrong parameter
4 Correct 4 ms 4588 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 18 ms 5200 KB wrong parameter
6 Incorrect 17 ms 5200 KB wrong parameter
7 Incorrect 65 ms 5412 KB wrong parameter
8 Incorrect 12 ms 4972 KB wrong parameter
9 Incorrect 13 ms 4920 KB wrong parameter
10 Incorrect 17 ms 4896 KB wrong parameter
11 Incorrect 20 ms 5076 KB wrong parameter
12 Incorrect 10 ms 4948 KB wrong parameter
13 Incorrect 72 ms 5616 KB wrong parameter
14 Incorrect 13 ms 4972 KB wrong parameter
15 Incorrect 15 ms 5028 KB wrong parameter
16 Incorrect 87 ms 5412 KB wrong parameter
17 Incorrect 50 ms 5348 KB wrong parameter
18 Incorrect 93 ms 5640 KB wrong parameter
19 Incorrect 33 ms 5364 KB wrong parameter
20 Incorrect 138 ms 6068 KB wrong parameter
21 Incorrect 129 ms 6144 KB wrong parameter
22 Incorrect 56 ms 5684 KB wrong parameter
23 Incorrect 138 ms 6340 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 416 ms 9972 KB wrong parameter
2 Correct 3 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 12 ms 5056 KB wrong parameter
4 Correct 4 ms 4588 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 18 ms 5200 KB wrong parameter
6 Incorrect 17 ms 5200 KB wrong parameter
7 Incorrect 65 ms 5412 KB wrong parameter
8 Incorrect 12 ms 4972 KB wrong parameter
9 Incorrect 13 ms 4920 KB wrong parameter
10 Incorrect 17 ms 4896 KB wrong parameter
11 Incorrect 20 ms 5076 KB wrong parameter
12 Incorrect 10 ms 4948 KB wrong parameter
13 Incorrect 72 ms 5616 KB wrong parameter
14 Incorrect 13 ms 4972 KB wrong parameter
15 Incorrect 15 ms 5028 KB wrong parameter
16 Incorrect 87 ms 5412 KB wrong parameter
17 Incorrect 50 ms 5348 KB wrong parameter
18 Incorrect 93 ms 5640 KB wrong parameter
19 Incorrect 33 ms 5364 KB wrong parameter
20 Incorrect 138 ms 6068 KB wrong parameter
21 Incorrect 129 ms 6144 KB wrong parameter
22 Incorrect 56 ms 5684 KB wrong parameter
23 Incorrect 138 ms 6340 KB wrong parameter