Submission #748034

#	Time	Username	Problem	Language	Result	Execution time	Memory
748034		finn__	Two Transportations (JOI19_transportations)	C++17	100 / 100	756 ms	48964 KiB

Azer

#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;
    if (azer::iterations < N)
        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; }

Baijan

#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 (stderr)

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)
      |                        ~~^~~
Azer.cpp:62:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   62 |     if (azer::iterations < N)
      |         ~~~~~~~~~~~~~~~~~^~~

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: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 10 / 10
• Subtask 7: 16 / 16