oj.uz

답안 #748009

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
748009 2023-05-25T09:36:18 Z finn__ Two Transportations (JOI19_transportations) C++17
0 / 100
 454 ms 13300 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;
    size_t iterations, receive_iterations;
    int max_fixed_distance, status, receive_buffer, next_distance;

    void process_node(int u)
    {
        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)
            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);
    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;
    size_t receive_iterations;
    int max_fixed_distance, status, receive_buffer, next_distance;

    void process_node(int u)
    {
        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);
    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::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:53:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   53 |     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:34:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   34 |     for (size_t i = 0; i < B; ++i)
      |                        ~~^~~

Subtask #1
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 656 KB Output is correct
2 Runtime error 0 ms 200 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 418 ms 716 KB Output is correct
2 Runtime error 0 ms 200 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 656 KB Output is correct
2 Correct 214 ms 612 KB Output is correct
3 Incorrect 326 ms 13300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 656 KB Output is correct
2 Correct 214 ms 612 KB Output is correct
3 Incorrect 326 ms 13300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 196 ms 656 KB Output is correct
2 Correct 214 ms 612 KB Output is correct
3 Incorrect 326 ms 13300 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 454 ms 656 KB Output is correct
2 Runtime error 0 ms 200 KB Execution failed because the return code was nonzero
3 Halted 0 ms 0 KB -