oj.uz

Submission #748023

# Submission time Handle Problem Language Result Execution time Memory
748023 2023-05-25T09:59:41 Z finn__ Two Transportations (JOI19_transportations) C++17
0 / 100
 442 ms 35584 KB 
#include "Azer.h"
#include <vector>
#include <queue>
#include <cstdlib>

/*
status: 0 -> initialize round
        1 -> receive distance
        2 -> distance received
        3 -> receive node
        4 -> node received
*/

namespace azer // neccessary to avoid naming conflicts :(
{
    std::vector<std::vector<std::pair<int, int>>> g;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
    std::vector<int> d;
    std::vector<bool> finished;
    size_t iterations, receive_iterations;
    int max_fixed_distance, status, receive_buffer, next_distance;

    void process_node(int u)
    {
        finished[u] = 1;
        max_fixed_distance = std::max(max_fixed_distance, d[u]);
        for (auto const &[v, w] : g[u])
            if (d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                q.emplace(d[v], v);
            }
    }

    void send_int(int x, size_t num_bits)
    {
        for (size_t i = 0; i < num_bits; ++i)
            SendA((x >> i) & 1);
    }

    void send_current_best()
    {
        while (!q.empty() && (d[q.top().second] != q.top().first || finished[q.top().second]))
            q.pop();
        if (q.empty())
            send_int(511, 9);
        else
            send_int(q.top().first - max_fixed_distance, 9);
    }
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C)
{
    azer::g.resize(N);
    for (size_t i = 0; i < A; ++i)
        azer::g[U[i]].emplace_back(V[i], C[i]), azer::g[V[i]].emplace_back(U[i], C[i]);
    azer::d.resize(N);
    azer::finished.resize(N);
    fill(azer::d.begin() + 1, azer::d.end(), 1000001);
    azer::process_node(0);
    azer::iterations = 1;
    azer::send_current_best();
    azer::status = 1;
}

void ReceiveA(bool x)
{
    if (!azer::status)
    {
        azer::send_current_best();
        azer::receive_buffer = azer::receive_iterations = 0;
        azer::status = 1;
    }
    else if (azer::status == 1)
    {
        azer::receive_buffer |= x << azer::receive_iterations;
        azer::receive_iterations++;
        if (azer::receive_iterations == 9)
        {
            azer::status = 2;
            ReceiveA(0);
        }
    }
    else if (azer::status == 2)
    {
        if (azer::receive_buffer == 511)
        {
            if (azer::q.empty())
                exit(1);
            azer::send_int(azer::q.top().second, 11);
            azer::next_distance = azer::q.top().first;
            azer::receive_buffer = azer::q.top().second;
            azer::q.pop();
            azer::status = 4;
            ReceiveA(0);
        }
        else
        {
            azer::next_distance = azer::max_fixed_distance + azer::receive_buffer;
            azer::receive_buffer = azer::receive_iterations = 0;
            azer::status = 3;
        }
    }
    else if (azer::status == 3)
    {
        azer::receive_buffer |= x << azer::receive_iterations;
        azer::receive_iterations++;
        if (azer::receive_iterations == 11)
        {
            azer::status = 4;
            ReceiveA(0);
        }
    }
    else
    {
        azer::d[azer::receive_buffer] = azer::next_distance;
        azer::process_node(azer::receive_buffer);
        ++azer::iterations;
        if (azer::iterations < azer::g.size())
        {
            azer::status = 0;
            ReceiveA(0);
        }
    }
}

std::vector<int> Answer() { return azer::d; }
#include "Baijan.h"
#include <vector>
#include <queue>

namespace baijan
{
    std::vector<std::vector<std::pair<int, int>>> g;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> q;
    std::vector<int> d;
    std::vector<bool> finished;
    size_t receive_iterations;
    int max_fixed_distance, status, receive_buffer, next_distance;

    void process_node(int u)
    {
        finished[u] = 1;
        max_fixed_distance = std::max(max_fixed_distance, d[u]);
        for (auto const &[v, w] : g[u])
            if (d[u] + w < d[v])
            {
                d[v] = d[u] + w;
                q.emplace(d[v], v);
            }
    }

    void send_int(int x, size_t num_bits)
    {
        for (size_t i = 0; i < num_bits; ++i)
            SendB((x >> i) & 1);
    }
}

void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D)
{
    baijan::g.resize(N);
    for (size_t i = 0; i < B; ++i)
        baijan::g[S[i]].emplace_back(T[i], D[i]), baijan::g[T[i]].emplace_back(S[i], D[i]);
    baijan::d.resize(N);
    baijan::finished.resize(N);
    fill(baijan::d.begin() + 1, baijan::d.end(), 1000001);
    baijan::process_node(0);
    baijan::status = 1;
}

void ReceiveB(bool y)
{
    if (!baijan::status)
    {
        baijan::receive_buffer = baijan::receive_iterations = 0;
        baijan::status = 1;
    }
    else if (baijan::status == 1)
    {
        baijan::receive_buffer |= y << baijan::receive_iterations;
        baijan::receive_iterations++;
        if (baijan::receive_iterations == 9)
        {
            baijan::status = 2;
            ReceiveB(0);
        }
    }
    else if (baijan::status == 2)
    {
        while (!baijan::q.empty() &&
               (baijan::d[baijan::q.top().second] != baijan::q.top().first ||
                baijan::finished[baijan::q.top().second]))
            baijan::q.pop();
        if (!baijan::q.empty() &&
            baijan::q.top().first < baijan::max_fixed_distance + baijan::receive_buffer)
        {
            baijan::send_int(baijan::q.top().first - baijan::max_fixed_distance, 9);
            baijan::send_int(baijan::q.top().second, 11);
            baijan::next_distance = baijan::q.top().first;
            baijan::receive_buffer = baijan::q.top().second;
            baijan::q.pop();
            baijan::status = 4;
            ReceiveB(0);
        }
        else
        {
            baijan::send_int(511, 9);
            baijan::next_distance = baijan::max_fixed_distance + baijan::receive_buffer;
            baijan::receive_buffer = baijan::receive_iterations = 0;
            baijan::status = 3;
        }
    }
    else if (baijan::status == 3)
    {
        baijan::receive_buffer |= y << baijan::receive_iterations;
        baijan::receive_iterations++;
        if (baijan::receive_iterations == 11)
        {
            baijan::status = 4;
            ReceiveB(0);
        }
    }
    else
    {
        baijan::d[baijan::receive_buffer] = baijan::next_distance;
        baijan::process_node(baijan::receive_buffer);
        baijan::status = 0;
        ReceiveB(0);
    }
}

Compilation message

Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:55:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   55 |     for (size_t i = 0; i < A; ++i)
      |                        ~~^~~

Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:36:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |     for (size_t i = 0; i < B; ++i)
      |                        ~~^~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 784 KB Output is correct
2 Runtime error 1 ms 200 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 0 ms 200 KB Execution failed because the return code was nonzero
2 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 442 ms 716 KB Output is correct
2 Runtime error 1 ms 200 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 656 KB Output is correct
2 Correct 285 ms 612 KB Output is correct
3 Correct 301 ms 13300 KB Output is correct
4 Correct 164 ms 628 KB Output is correct
5 Correct 226 ms 9996 KB Output is correct
6 Correct 166 ms 656 KB Output is correct
7 Correct 230 ms 636 KB Output is correct
8 Correct 219 ms 656 KB Output is correct
9 Correct 234 ms 18060 KB Output is correct
10 Correct 226 ms 18232 KB Output is correct
11 Correct 392 ms 35584 KB Output is correct
12 Correct 360 ms 30672 KB Output is correct
13 Correct 238 ms 656 KB Output is correct
14 Runtime error 0 ms 296 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 656 KB Output is correct
2 Correct 285 ms 612 KB Output is correct
3 Correct 301 ms 13300 KB Output is correct
4 Correct 164 ms 628 KB Output is correct
5 Correct 226 ms 9996 KB Output is correct
6 Correct 166 ms 656 KB Output is correct
7 Correct 230 ms 636 KB Output is correct
8 Correct 219 ms 656 KB Output is correct
9 Correct 234 ms 18060 KB Output is correct
10 Correct 226 ms 18232 KB Output is correct
11 Correct 392 ms 35584 KB Output is correct
12 Correct 360 ms 30672 KB Output is correct
13 Correct 238 ms 656 KB Output is correct
14 Runtime error 0 ms 296 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 241 ms 656 KB Output is correct
2 Correct 285 ms 612 KB Output is correct
3 Correct 301 ms 13300 KB Output is correct
4 Correct 164 ms 628 KB Output is correct
5 Correct 226 ms 9996 KB Output is correct
6 Correct 166 ms 656 KB Output is correct
7 Correct 230 ms 636 KB Output is correct
8 Correct 219 ms 656 KB Output is correct
9 Correct 234 ms 18060 KB Output is correct
10 Correct 226 ms 18232 KB Output is correct
11 Correct 392 ms 35584 KB Output is correct
12 Correct 360 ms 30672 KB Output is correct
13 Correct 238 ms 656 KB Output is correct
14 Runtime error 0 ms 296 KB Execution failed because the return code was nonzero
15 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 399 ms 784 KB Output is correct
2 Runtime error 1 ms 200 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -