oj.uz

Submission #476981

# Submission time Handle Problem Language Result Execution time Memory
476981 2021-09-29T16:19:11 Z wiktoria_bazan Saveit (IOI10_saveit) C++14
0 / 100
 322 ms 9720 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;
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 koduj_drzewo(int nv) {
    for (int v = 0; v < nv; v++) {
        ll_to_bits(ojciec[v], 10);
    }
}

void odl(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 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);
    odl(nv);
    for (int h = 1; h < nh; h++) {
        bfs(h);
        odl(nv);
    }
    return;
}

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

const int N = 1e3 + 9;
int O[N];
vector<int> G[N];
int odl[N];
int d[N];

bool odw[N];
bool ost = true;

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

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;
    }
    G[o].push_back(v);
  }
}

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

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

void fczytaj_odl(int nh, int nv){
  for(int h = 0; h < nh; h++){
    int a = 0, mn = 1;
    for(int i = 0; i < 58; i++){
      int bit = decode_bit();
      a += mn * bit;
      mn <<= 1;
    }
    odzyskaj(a, nv);
    d[h] = 0;
    policz(h);
    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:25:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |         for (int i = 0; i < G[v].size(); i++) {
      |                         ~~^~~~~~~~~~~~~
encoder.cpp: In function 'void dfs(int, int)':
encoder.cpp:40:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for (int i = 0; i < G[v].size(); i++) {
      |                     ~~^~~~~~~~~~~~~

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

Subtask #1
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 9720 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 10 ms 4964 KB Output isn't correct
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 11 ms 5092 KB wrong parameter
6 Incorrect 9 ms 5204 KB wrong parameter
7 Incorrect 43 ms 5380 KB wrong parameter
8 Incorrect 10 ms 4964 KB wrong parameter
9 Incorrect 10 ms 4976 KB wrong parameter
10 Incorrect 9 ms 4964 KB wrong parameter
11 Incorrect 11 ms 5176 KB wrong parameter
12 Incorrect 9 ms 4964 KB wrong parameter
13 Incorrect 27 ms 5580 KB wrong parameter
14 Incorrect 9 ms 4984 KB wrong parameter
15 Incorrect 10 ms 5072 KB wrong parameter
16 Incorrect 54 ms 5636 KB wrong parameter
17 Incorrect 31 ms 5544 KB wrong parameter
18 Incorrect 36 ms 5856 KB wrong parameter
19 Incorrect 32 ms 5320 KB wrong parameter
20 Incorrect 40 ms 5916 KB wrong parameter
21 Incorrect 59 ms 6040 KB wrong parameter
22 Incorrect 35 ms 5596 KB wrong parameter
23 Incorrect 55 ms 6420 KB wrong parameter

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 9720 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 10 ms 4964 KB Output isn't correct
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 11 ms 5092 KB wrong parameter
6 Incorrect 9 ms 5204 KB wrong parameter
7 Incorrect 43 ms 5380 KB wrong parameter
8 Incorrect 10 ms 4964 KB wrong parameter
9 Incorrect 10 ms 4976 KB wrong parameter
10 Incorrect 9 ms 4964 KB wrong parameter
11 Incorrect 11 ms 5176 KB wrong parameter
12 Incorrect 9 ms 4964 KB wrong parameter
13 Incorrect 27 ms 5580 KB wrong parameter
14 Incorrect 9 ms 4984 KB wrong parameter
15 Incorrect 10 ms 5072 KB wrong parameter
16 Incorrect 54 ms 5636 KB wrong parameter
17 Incorrect 31 ms 5544 KB wrong parameter
18 Incorrect 36 ms 5856 KB wrong parameter
19 Incorrect 32 ms 5320 KB wrong parameter
20 Incorrect 40 ms 5916 KB wrong parameter
21 Incorrect 59 ms 6040 KB wrong parameter
22 Incorrect 35 ms 5596 KB wrong parameter
23 Incorrect 55 ms 6420 KB wrong parameter

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 9720 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 10 ms 4964 KB Output isn't correct
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 11 ms 5092 KB wrong parameter
6 Incorrect 9 ms 5204 KB wrong parameter
7 Incorrect 43 ms 5380 KB wrong parameter
8 Incorrect 10 ms 4964 KB wrong parameter
9 Incorrect 10 ms 4976 KB wrong parameter
10 Incorrect 9 ms 4964 KB wrong parameter
11 Incorrect 11 ms 5176 KB wrong parameter
12 Incorrect 9 ms 4964 KB wrong parameter
13 Incorrect 27 ms 5580 KB wrong parameter
14 Incorrect 9 ms 4984 KB wrong parameter
15 Incorrect 10 ms 5072 KB wrong parameter
16 Incorrect 54 ms 5636 KB wrong parameter
17 Incorrect 31 ms 5544 KB wrong parameter
18 Incorrect 36 ms 5856 KB wrong parameter
19 Incorrect 32 ms 5320 KB wrong parameter
20 Incorrect 40 ms 5916 KB wrong parameter
21 Incorrect 59 ms 6040 KB wrong parameter
22 Incorrect 35 ms 5596 KB wrong parameter
23 Incorrect 55 ms 6420 KB wrong parameter

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 322 ms 9720 KB Output isn't correct
2 Incorrect 2 ms 4580 KB Output isn't correct
3 Incorrect 10 ms 4964 KB Output isn't correct
4 Incorrect 3 ms 4588 KB Output isn't correct
5 Incorrect 11 ms 5092 KB wrong parameter
6 Incorrect 9 ms 5204 KB wrong parameter
7 Incorrect 43 ms 5380 KB wrong parameter
8 Incorrect 10 ms 4964 KB wrong parameter
9 Incorrect 10 ms 4976 KB wrong parameter
10 Incorrect 9 ms 4964 KB wrong parameter
11 Incorrect 11 ms 5176 KB wrong parameter
12 Incorrect 9 ms 4964 KB wrong parameter
13 Incorrect 27 ms 5580 KB wrong parameter
14 Incorrect 9 ms 4984 KB wrong parameter
15 Incorrect 10 ms 5072 KB wrong parameter
16 Incorrect 54 ms 5636 KB wrong parameter
17 Incorrect 31 ms 5544 KB wrong parameter
18 Incorrect 36 ms 5856 KB wrong parameter
19 Incorrect 32 ms 5320 KB wrong parameter
20 Incorrect 40 ms 5916 KB wrong parameter
21 Incorrect 59 ms 6040 KB wrong parameter
22 Incorrect 35 ms 5596 KB wrong parameter
23 Incorrect 55 ms 6420 KB wrong parameter