oj.uz

Submission #940885

# Submission time Handle Problem Language Result Execution time Memory
940885 2024-03-07T23:30:22 Z ThegeekKnight16 Saveit (IOI10_saveit) C++17
25 / 100
 207 ms 21416 KB 
#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);
}

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

Compilation message

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 21416 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 11280 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 11876 KB Output is correct - 69690 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 40 ms 14108 KB Output is partially correct - 183850 call(s) of encode_bit()
6 Correct 47 ms 14488 KB Output is partially correct - 188290 call(s) of encode_bit()
7 Correct 78 ms 17308 KB Output is partially correct - 362010 call(s) of encode_bit()
8 Correct 17 ms 11516 KB Output is correct - 36530 call(s) of encode_bit()
9 Correct 18 ms 11396 KB Output is correct - 41030 call(s) of encode_bit()
10 Correct 16 ms 11356 KB Output is correct - 38950 call(s) of encode_bit()
11 Correct 27 ms 14060 KB Output is partially correct - 94710 call(s) of encode_bit()
12 Correct 13 ms 11376 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 71 ms 16692 KB Output is partially correct - 241570 call(s) of encode_bit()
14 Correct 19 ms 11688 KB Output is correct - 45450 call(s) of encode_bit()
15 Correct 21 ms 11596 KB Output is correct - 48550 call(s) of encode_bit()
16 Correct 41 ms 14508 KB Output is partially correct - 107030 call(s) of encode_bit()
17 Correct 38 ms 14288 KB Output is partially correct - 99230 call(s) of encode_bit()
18 Correct 57 ms 14692 KB Output is partially correct - 162330 call(s) of encode_bit()
19 Correct 51 ms 14628 KB Output is partially correct - 170990 call(s) of encode_bit()
20 Correct 66 ms 18924 KB Output is partially correct - 209830 call(s) of encode_bit()
21 Correct 75 ms 19144 KB Output is partially correct - 222830 call(s) of encode_bit()
22 Correct 77 ms 17156 KB Output is partially correct - 337210 call(s) of encode_bit()
23 Correct 89 ms 19844 KB Output is partially correct - 311990 call(s) of encode_bit()

Subtask #2
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 21416 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 11280 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 11876 KB Output is correct - 69690 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 40 ms 14108 KB Output is partially correct - 183850 call(s) of encode_bit()
6 Correct 47 ms 14488 KB Output is partially correct - 188290 call(s) of encode_bit()
7 Correct 78 ms 17308 KB Output is partially correct - 362010 call(s) of encode_bit()
8 Correct 17 ms 11516 KB Output is correct - 36530 call(s) of encode_bit()
9 Correct 18 ms 11396 KB Output is correct - 41030 call(s) of encode_bit()
10 Correct 16 ms 11356 KB Output is correct - 38950 call(s) of encode_bit()
11 Correct 27 ms 14060 KB Output is partially correct - 94710 call(s) of encode_bit()
12 Correct 13 ms 11376 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 71 ms 16692 KB Output is partially correct - 241570 call(s) of encode_bit()
14 Correct 19 ms 11688 KB Output is correct - 45450 call(s) of encode_bit()
15 Correct 21 ms 11596 KB Output is correct - 48550 call(s) of encode_bit()
16 Correct 41 ms 14508 KB Output is partially correct - 107030 call(s) of encode_bit()
17 Correct 38 ms 14288 KB Output is partially correct - 99230 call(s) of encode_bit()
18 Correct 57 ms 14692 KB Output is partially correct - 162330 call(s) of encode_bit()
19 Correct 51 ms 14628 KB Output is partially correct - 170990 call(s) of encode_bit()
20 Correct 66 ms 18924 KB Output is partially correct - 209830 call(s) of encode_bit()
21 Correct 75 ms 19144 KB Output is partially correct - 222830 call(s) of encode_bit()
22 Correct 77 ms 17156 KB Output is partially correct - 337210 call(s) of encode_bit()
23 Correct 89 ms 19844 KB Output is partially correct - 311990 call(s) of encode_bit()

Subtask #3
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 21416 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 11280 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 11876 KB Output is correct - 69690 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 40 ms 14108 KB Output is partially correct - 183850 call(s) of encode_bit()
6 Correct 47 ms 14488 KB Output is partially correct - 188290 call(s) of encode_bit()
7 Correct 78 ms 17308 KB Output is partially correct - 362010 call(s) of encode_bit()
8 Correct 17 ms 11516 KB Output is correct - 36530 call(s) of encode_bit()
9 Correct 18 ms 11396 KB Output is correct - 41030 call(s) of encode_bit()
10 Correct 16 ms 11356 KB Output is correct - 38950 call(s) of encode_bit()
11 Correct 27 ms 14060 KB Output is partially correct - 94710 call(s) of encode_bit()
12 Correct 13 ms 11376 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 71 ms 16692 KB Output is partially correct - 241570 call(s) of encode_bit()
14 Correct 19 ms 11688 KB Output is correct - 45450 call(s) of encode_bit()
15 Correct 21 ms 11596 KB Output is correct - 48550 call(s) of encode_bit()
16 Correct 41 ms 14508 KB Output is partially correct - 107030 call(s) of encode_bit()
17 Correct 38 ms 14288 KB Output is partially correct - 99230 call(s) of encode_bit()
18 Correct 57 ms 14692 KB Output is partially correct - 162330 call(s) of encode_bit()
19 Correct 51 ms 14628 KB Output is partially correct - 170990 call(s) of encode_bit()
20 Correct 66 ms 18924 KB Output is partially correct - 209830 call(s) of encode_bit()
21 Correct 75 ms 19144 KB Output is partially correct - 222830 call(s) of encode_bit()
22 Correct 77 ms 17156 KB Output is partially correct - 337210 call(s) of encode_bit()
23 Correct 89 ms 19844 KB Output is partially correct - 311990 call(s) of encode_bit()

Subtask #4
0.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 207 ms 21416 KB Output is partially correct - 354610 call(s) of encode_bit()
2 Correct 2 ms 11280 KB Output is correct - 150 call(s) of encode_bit()
3 Correct 23 ms 11876 KB Output is correct - 69690 call(s) of encode_bit()
4 Correct 2 ms 11268 KB Output is correct - 190 call(s) of encode_bit()
5 Correct 40 ms 14108 KB Output is partially correct - 183850 call(s) of encode_bit()
6 Correct 47 ms 14488 KB Output is partially correct - 188290 call(s) of encode_bit()
7 Correct 78 ms 17308 KB Output is partially correct - 362010 call(s) of encode_bit()
8 Correct 17 ms 11516 KB Output is correct - 36530 call(s) of encode_bit()
9 Correct 18 ms 11396 KB Output is correct - 41030 call(s) of encode_bit()
10 Correct 16 ms 11356 KB Output is correct - 38950 call(s) of encode_bit()
11 Correct 27 ms 14060 KB Output is partially correct - 94710 call(s) of encode_bit()
12 Correct 13 ms 11376 KB Output is correct - 19990 call(s) of encode_bit()
13 Correct 71 ms 16692 KB Output is partially correct - 241570 call(s) of encode_bit()
14 Correct 19 ms 11688 KB Output is correct - 45450 call(s) of encode_bit()
15 Correct 21 ms 11596 KB Output is correct - 48550 call(s) of encode_bit()
16 Correct 41 ms 14508 KB Output is partially correct - 107030 call(s) of encode_bit()
17 Correct 38 ms 14288 KB Output is partially correct - 99230 call(s) of encode_bit()
18 Correct 57 ms 14692 KB Output is partially correct - 162330 call(s) of encode_bit()
19 Correct 51 ms 14628 KB Output is partially correct - 170990 call(s) of encode_bit()
20 Correct 66 ms 18924 KB Output is partially correct - 209830 call(s) of encode_bit()
21 Correct 75 ms 19144 KB Output is partially correct - 222830 call(s) of encode_bit()
22 Correct 77 ms 17156 KB Output is partially correct - 337210 call(s) of encode_bit()
23 Correct 89 ms 19844 KB Output is partially correct - 311990 call(s) of encode_bit()