제출 #477150

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
477150		wiktoria_bazan	저장 (Saveit) (IOI10_saveit)	C++14	0 / 100	236 ms	9792 KiB

encoder

#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);
  }
}

decoder

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25