oj.uz

Submission #477150

# Submission time Handle Problem Language Result Execution time Memory
477150 2021-09-30T22:41:27 Z wiktoria_bazan Saveit (IOI10_saveit) C++14
0 / 100
 236 ms 9792 KB 
#include "grader.h"
#include "encoder.h"
#include<iostream>
#include<vector>
#include<queue>
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;
    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>
using namespace std;

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

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

void policz(int v) {
    odw[v] = ost;
    d[v] = d[O[v]] + odl[v];
    for (int i = 0; i < G2[v].size(); i++) {
        int syn = G2[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;
        G2[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:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |     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 < G2[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~~

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 9792 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 11 ms 4944 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 17 ms 5212 KB wrong parameter
6 Incorrect 13 ms 5220 KB wrong parameter
7 Incorrect 56 ms 5540 KB wrong parameter
8 Incorrect 11 ms 4944 KB wrong parameter
9 Incorrect 13 ms 4944 KB wrong parameter
10 Incorrect 12 ms 4944 KB wrong parameter
11 Incorrect 19 ms 5072 KB wrong parameter
12 Incorrect 10 ms 4944 KB wrong parameter
13 Incorrect 44 ms 5596 KB wrong parameter
14 Incorrect 12 ms 4964 KB wrong parameter
15 Incorrect 12 ms 5096 KB wrong parameter
16 Incorrect 47 ms 5484 KB wrong parameter
17 Incorrect 52 ms 5420 KB wrong parameter
18 Incorrect 37 ms 5772 KB wrong parameter
19 Incorrect 22 ms 5356 KB wrong parameter
20 Incorrect 84 ms 5988 KB wrong parameter
21 Incorrect 141 ms 6072 KB wrong parameter
22 Incorrect 54 ms 5644 KB wrong parameter
23 Incorrect 121 ms 6300 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 9792 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 11 ms 4944 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 17 ms 5212 KB wrong parameter
6 Incorrect 13 ms 5220 KB wrong parameter
7 Incorrect 56 ms 5540 KB wrong parameter
8 Incorrect 11 ms 4944 KB wrong parameter
9 Incorrect 13 ms 4944 KB wrong parameter
10 Incorrect 12 ms 4944 KB wrong parameter
11 Incorrect 19 ms 5072 KB wrong parameter
12 Incorrect 10 ms 4944 KB wrong parameter
13 Incorrect 44 ms 5596 KB wrong parameter
14 Incorrect 12 ms 4964 KB wrong parameter
15 Incorrect 12 ms 5096 KB wrong parameter
16 Incorrect 47 ms 5484 KB wrong parameter
17 Incorrect 52 ms 5420 KB wrong parameter
18 Incorrect 37 ms 5772 KB wrong parameter
19 Incorrect 22 ms 5356 KB wrong parameter
20 Incorrect 84 ms 5988 KB wrong parameter
21 Incorrect 141 ms 6072 KB wrong parameter
22 Incorrect 54 ms 5644 KB wrong parameter
23 Incorrect 121 ms 6300 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 9792 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 11 ms 4944 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 17 ms 5212 KB wrong parameter
6 Incorrect 13 ms 5220 KB wrong parameter
7 Incorrect 56 ms 5540 KB wrong parameter
8 Incorrect 11 ms 4944 KB wrong parameter
9 Incorrect 13 ms 4944 KB wrong parameter
10 Incorrect 12 ms 4944 KB wrong parameter
11 Incorrect 19 ms 5072 KB wrong parameter
12 Incorrect 10 ms 4944 KB wrong parameter
13 Incorrect 44 ms 5596 KB wrong parameter
14 Incorrect 12 ms 4964 KB wrong parameter
15 Incorrect 12 ms 5096 KB wrong parameter
16 Incorrect 47 ms 5484 KB wrong parameter
17 Incorrect 52 ms 5420 KB wrong parameter
18 Incorrect 37 ms 5772 KB wrong parameter
19 Incorrect 22 ms 5356 KB wrong parameter
20 Incorrect 84 ms 5988 KB wrong parameter
21 Incorrect 141 ms 6072 KB wrong parameter
22 Incorrect 54 ms 5644 KB wrong parameter
23 Incorrect 121 ms 6300 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 236 ms 9792 KB wrong parameter
2 Correct 2 ms 4580 KB Output is correct - 254 call(s) of encode_bit()
3 Incorrect 11 ms 4944 KB wrong parameter
4 Correct 2 ms 4580 KB Output is correct - 390 call(s) of encode_bit()
5 Incorrect 17 ms 5212 KB wrong parameter
6 Incorrect 13 ms 5220 KB wrong parameter
7 Incorrect 56 ms 5540 KB wrong parameter
8 Incorrect 11 ms 4944 KB wrong parameter
9 Incorrect 13 ms 4944 KB wrong parameter
10 Incorrect 12 ms 4944 KB wrong parameter
11 Incorrect 19 ms 5072 KB wrong parameter
12 Incorrect 10 ms 4944 KB wrong parameter
13 Incorrect 44 ms 5596 KB wrong parameter
14 Incorrect 12 ms 4964 KB wrong parameter
15 Incorrect 12 ms 5096 KB wrong parameter
16 Incorrect 47 ms 5484 KB wrong parameter
17 Incorrect 52 ms 5420 KB wrong parameter
18 Incorrect 37 ms 5772 KB wrong parameter
19 Incorrect 22 ms 5356 KB wrong parameter
20 Incorrect 84 ms 5988 KB wrong parameter
21 Incorrect 141 ms 6072 KB wrong parameter
22 Incorrect 54 ms 5644 KB wrong parameter
23 Incorrect 121 ms 6300 KB wrong parameter