Submission #927946

#	Time	Username	Problem	Language	Result	Execution time	Memory
927946		boris_mihov	Two Transportations (JOI19_transportations)	C++17	0 / 100	179 ms	820 KiB

Azer

#include "Azer.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int DIST_BITS = 9;
const int NODE_BITS = 11;
const int MAXN = 2000 + 10;
const int MAXM = 500000 + 10;
const int INF  = 1e9;

static int n, m;
static int lastDist;
static int dist[MAXN];
static bool vis[MAXN];

struct PQelement
{
    int node;
    int currDist;

    friend bool operator < (const PQelement &a, const PQelement &b)
    {
        return a.currDist > b.currDist || (a.currDist == b.currDist && a.node > b.node);
    }
};

static std::vector <std::pair <int,int>> g[MAXN];
static std::priority_queue <PQelement> pq;
static std::queue <int> receivedQueue;

int readA(int);
void writeA(int, int);
std::pair <int,int> readPair()
{
    if (receivedQueue.front() == 1)
    {
        receivedQueue.pop();
        return {n, 1e9};
    }

    receivedQueue.pop();
    return {readA(NODE_BITS), readA(DIST_BITS)};
}

void receivePairA()
{   
    auto [otherNode, otherDist] = readPair();
    // std::cout << "receive from B: " << otherNode << ' ' << otherDist << '\n';
    otherDist += lastDist;

    if (otherNode < n) pq.push({otherNode, otherDist});
    // std::cout << "topA: " << pq.top().node << ' ' << pq.top().currDist << ' ' << lastDist << '\n';
    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }

    if (pq.size())
    {
        // std::cout << "hereAAA: " << pq.top().currDist << ' ' << lastDist << '\n';
        auto [node, currDist] = pq.top();
        pq.pop();

        vis[node] = true;
        dist[node] = currDist;
        lastDist = currDist;
        for (const auto &[u, edge] : g[node])
        {
            if (dist[u] > dist[node] + edge)
            {
                dist[u] = dist[node] + edge;
                pq.push({u, dist[u]});
            }
        }
    }

    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }

    if (pq.size())
    {
        // std::cout << "send from A: " << pq.top().node << ' ' << pq.top().currDist << '\n';
        writeA(pq.top().node, NODE_BITS);
        writeA(pq.top().currDist - lastDist, DIST_BITS);
    } else if (otherNode != n + 1)
    {
        // std::cout << "send from A: " << n << ' ' << -1 << '\n';
        writeA(n, NODE_BITS);
        writeA(0, DIST_BITS);
    }
}

void ReceiveA(bool x) 
{
    receivedQueue.push(x);
    if (receivedQueue.size() == NODE_BITS + DIST_BITS + 1 || (receivedQueue.size() == 1 && receivedQueue.front() == 1))
    {
        receivePairA();
    }
}

int readA(int bits)
{
    int res = 0;
    for (int i = 0 ; i < bits ; ++i)
    {
        res <<= 1;
        // std::cout << "bitA: " << receivedQueue.front() << ' ' << res << '\n';
        res += receivedQueue.front();
        receivedQueue.pop();
    }

    return res;
}

void writeA(int number, int bits)
{
    for (int i = bits - 1 ; i >= 0 ; --i)
    {
        SendA((number & (1 << i)) > 0);
    }
}

void InitA(int N, int A, std::vector <int> U, std::vector <int> V,std::vector <int> C)
{
    n = N; m = A;
    for (int i = 0 ; i < A ; ++i)
    {
        g[U[i]].push_back({V[i], C[i]});
        g[V[i]].push_back({U[i], C[i]});
    }

    std::fill(dist, dist + n, INF);
    pq.push({0, 0});

    writeA(0, NODE_BITS);
    writeA(0, DIST_BITS);
    dist[0] = 0;
}

std::vector <int> Answer() 
{
    std::vector <int> answer(n);
    for (int i = 0 ; i < n ; ++i)
    {
        answer[i] = dist[i];
    }

    return answer;
}

Baijan

#include "Baijan.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <vector>
#include <queue>

typedef long long llong;
const int DIST_BITS = 9;
const int NODE_BITS = 11;
const int MAXN = 2000 + 10;
const int MAXM = 500000 + 10;
const int INF  = 1e9;

static int n, m;
static int lastDist;
static int dist[MAXN];
static bool vis[MAXN];
static std::vector <std::pair <int,int>> g[MAXN];

struct PQelement
{
    int node;
    int currDist;

    friend bool operator < (const PQelement &a, const PQelement &b)
    {
        return a.currDist > b.currDist || (a.currDist == b.currDist && a.node > b.node);
    }
};

static std::priority_queue <PQelement> pq;
static std::queue <int> receivedQueue;

int readB(int);
void writeB(int, int);
void receivePairB();

void ReceiveB(bool x) 
{
    receivedQueue.push(x);
    if (receivedQueue.size() == NODE_BITS + DIST_BITS)
    {
        receivePairB();
    }
}

void receivePairB()
{   
    int otherNode = readB(NODE_BITS);
    int otherDist = lastDist + readB(DIST_BITS);
    if (otherNode < n) pq.push({otherNode, otherDist});
    // std::cout << "from A: " << otherNode << ' ' << otherDist - lastDist << '\n';
    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }

    bool whatShouldSend = false;
    bool isEmpty = true;

    if (pq.size() && (otherNode >= n || pq.top().currDist < otherDist))
    {
        // std::cout << "send from B: " << pq.top().node << ' ' << pq.top().currDist << ' ' << lastDist << '\n';
        SendB(0);
        writeB(pq.top().node, NODE_BITS);
        writeB(pq.top().currDist - lastDist, DIST_BITS);
    } else if (otherNode != n)
    {
        whatShouldSend = true;
    }

    if (pq.size())
    {
        auto [node, currDist] = pq.top();
        isEmpty = false;
        // std::cout << "topB: " << node << ' ' << currDist  << "\n";
        pq.pop();

        vis[node] = true;
        dist[node] = currDist;
        lastDist = currDist;
        for (const auto &[u, edge] : g[node])
        {
            // std::cout << "B edge: " << u << ' ' << node << ' ' << edge << ' ' << dist[u] << ' ' << dist[node] + edge << '\n';
            if (dist[u] > dist[node] + edge)
            {
                dist[u] = dist[node] + edge;
                // assert(!vispu)
                pq.push({u, dist[u]});
            }
        }
    }

    if  (whatShouldSend)
    {
        if (pq.size() || !isEmpty) SendB(1);
        else
        {
            SendB(0);
            writeB(n + 1, NODE_BITS);
            writeB(lastDist, DIST_BITS);
        }
    }

    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }
}

int readB(int bits)
{
    int res = 0;
    for (int i = 0 ; i < bits ; ++i)
    {
        res <<= 1;
        res += receivedQueue.front();
        receivedQueue.pop();
    }

    return res;
}

void writeB(int number, int bits)
{
    for (int i = bits - 1 ; i >= 0 ; --i)
    {
        // std::cout << "bitB: " << number << ' ' << (number & (1 << i)) << ' ' << ((number & (1 << i)) > 0) << '\n';
        SendB((number & (1 << i)) > 0);
    }
}

void InitB(int N, int B, std::vector <int> U, std::vector <int> V, std::vector <int> C)
{
    n = N; m = B;
    for (int i = 0 ; i < B ; ++i)
    {
        g[U[i]].push_back({V[i], C[i]});
        g[V[i]].push_back({U[i], C[i]});
    }

    std::fill(dist, dist + n, INF);
    pq.push({0, 0});
    dist[0] = 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 0 / 38
• Subtask 5: 0 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16