제출 #940885

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
940885		ThegeekKnight16	저장 (Saveit) (IOI10_saveit)	C++17	25 / 100	207 ms	21416 KiB

encoder

#include <bits/stdc++.h>
#include "grader.h"
#include "encoder.h"
using namespace std;

void bfs(int S, int N, vector<vector<int>> &grafo, set<pair<int, int>> &edges)
{
    vector<int> Marc(N);
    queue<int> q; q.push(S); Marc[S] = 1;

    while (!q.empty())
    {
        int v = q.front(); q.pop();

        for (auto viz : grafo[v])
        {
            if (Marc[viz]) continue;
            Marc[viz] = 1;
            edges.emplace(min(v, viz), max(v, viz));
            q.push(viz);
        }
    }
}

void writeNum(int x)
{
    for (int i = 9; i >= 0; i--)
    {
        encode_bit(((x >> i)&1));
    }
}

void encode(int nv, int nh, int ne, int *v1, int *v2)
{
    int N = nv, H = nh, M = ne;
    vector<vector<int>> grafo(N);
    for (int i = 0; i < M; i++)
    {
        int X = v1[i], Y = v2[i];
        grafo[X].push_back(Y);
        grafo[Y].push_back(X);
    }

    set<pair<int, int>> edges;
    for (int i = 0; i < H; i++) bfs(i, N, grafo, edges);
    for (auto [X, Y] : edges)
    {
        writeNum(X);
        writeNum(Y);
    }
    writeNum(1023);
}

decoder

#include <bits/stdc++.h>
#include "grader.h"
#include "decoder.h"
using namespace std;

int readNum()
{
    int x = 0;
    for (int i = 0; i < 10; i++) x <<= 1, x += decode_bit();
    return x;
}

void bfs(int S, int N, vector<vector<int>> &grafo)
{
    vector<int> Marc(N), Dist(N);
    queue<int> q; q.push(S); Marc[S] = 1; Dist[S] = 0;

    while (!q.empty())
    {
        int v = q.front(); q.pop();

        for (auto viz : grafo[v])
        {
            if (Marc[viz]) continue;
            Dist[viz] = Dist[v] + 1;
            Marc[viz] = 1;
            q.push(viz);
        }
    }

    for (int i = 0; i < N; i++) hops(S, i, Dist[i]);
}

void decode(int nv, int nh)
{
    int N = nv, H = nh;
    vector<int> message;
    while (true)
    {
        int x = readNum();
        if (x == 1023) break;
        message.push_back(x);
    }

    vector<vector<int>> grafo(N);
    for (int i = 0; i < message.size(); i += 2)
    {
        int X = message[i], Y = message[i+1];
        grafo[X].push_back(Y);
        grafo[Y].push_back(X);
    }

    for (int i = 0; i < H; i++) bfs(i, N, grafo);
}

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

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

• Subtask 1: 25 / 25
• Subtask 2: 0 / 25
• Subtask 3: 0 / 25
• Subtask 4: 0 / 25