Submission #927979

#	Time	Username	Problem	Language	Result	Execution time	Memory
927979		boris_mihov	Two Transportations (JOI19_transportations)	C++17	68 / 100	517 ms	49060 KiB

Azer

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

typedef long long llong;
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 int DIST_BITS = 9;
static int NODE_BITS = 11;
static std::mt19937 rng(123456789);
static std::vector <bool> sequence;

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;
static int cntDoneTurns;
static int cntEntries;

int readA(int);
void writeA(int, int);
void manageA();

int getNodeA(int idx)
{
    if (idx == n + 1)
    {
        return n;
    }

    assert(idx != 0);
    // std::cout << "get node: " << idx << '\n' << std::flush;
    for (int i = 0 ; i < n ; ++i)
    {
        if (!vis[i] && idx == 1)
        {
            return i;
        }

        idx -= !vis[i];
    }

    assert(false);
}

int getIdxA(int node)
{
    int idx = 0;
    for (int i = 0 ; i <= node ; ++i)
    {
        idx += !vis[i];
    }

    // std::cout << "get idx: " << node << ' ' << idx << '\n' << std::flush;
    return idx;
}

std::pair <int,int> readPairA()
{
    if (receivedQueue.front() == 1)
    {
        receivedQueue.pop();
        return {n + 1, 1e9};
    }

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

void sendMyTopA()
{
    cntEntries++;
    while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
    {
        NODE_BITS--;
    }

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

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

    if (otherNode < n) pq.push({otherNode, otherDist});
    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }

    if (pq.size())
    {
        // std::cout << "hereAAA: " << pq.top().currDist << ' ' << lastDist << '\n';
        // std::cout << "topA: " << pq.top().node << ' ' << 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();
    }

    cntDoneTurns++;
    if (cntDoneTurns < n && sequence[cntDoneTurns] == 1)
    {
        SendA(0);
    }
}

void receiveResendPairA()
{   
    while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
    {
        NODE_BITS--;
    }

    cntEntries++;
    auto [otherNode, otherDist] = readPairA();
    otherNode = getNodeA(otherNode);
    otherDist += lastDist;
    if (otherNode < n) pq.push({otherNode, otherDist});
    // std::cout << "from A: " << otherNode << ' ' << otherDist << '\n';
    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }

    bool whatShouldSend = false;
    
    PQelement other = {otherNode, otherDist};
    // if (pq.size()) std::cout << "try b: " << pq.top().node << ' ' << pq.top().currDist << '\n';
    if (pq.size() && (otherNode >= n || other < pq.top()))
    {
        // std::cout << "send from B: " << pq.top().node << ' ' << pq.top().currDist << ' ' << lastDist << '\n';
        SendA(0);
        writeA(getIdxA(pq.top().node), NODE_BITS);
        writeA(pq.top().currDist - lastDist, DIST_BITS);
    } else if (pq.size())
    {
        SendA(1);
    }

    if (pq.size())
    {
        auto [node, currDist] = pq.top();
        // 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]});
            }
        }
    }

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

    cntDoneTurns++;
    if (cntDoneTurns < n && sequence[cntDoneTurns] == 1)
    {
        SendA(0);
    }
}

void ReceiveA(bool x) 
{
    while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
    {
        NODE_BITS--;
    }

    receivedQueue.push(x);
    if (cntEntries == cntDoneTurns && sequence[cntEntries] == 0)
    {
        receivedQueue.pop();
        manageA();
        return;
    }

    if (receivedQueue.size() == NODE_BITS + DIST_BITS + 1 || (receivedQueue.size() == 1 && receivedQueue.front() == 1))
    {
        if (sequence[cntDoneTurns] == 0) receiveSendPairA();
        else receiveResendPairA();
    }
}

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 manageA()
{
    sendMyTopA();
}

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

    while (sequence.size() < n)
    {
        sequence.push_back(rng() % 2);
    }

    sequence[0] = 0;
    std::fill(dist, dist + n, INF);
    pq.push({0, 0});
    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 <cassert>
#include <random>
#include <queue>

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

static int DIST_BITS = 9;
static int NODE_BITS = 11;
static int n, m;
static int lastDist;
static int dist[MAXN];
static bool vis[MAXN];
static std::vector <std::pair <int,int>> g[MAXN];
static std::mt19937 rng(123456789);
static std::vector <bool> sequence;
static int cntDoneTurns;
static int cntEntries;

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 receiveSendPairB();
void receiveResendPairB();
void manageB();

int getNodeB(int idx)
{
    if (idx == n + 1)
    {
        return n;
    }

    for (int i = 0 ; i < n ; ++i)
    {
        if (!vis[i] && idx == 1)
        {
            return i;
        }

        idx -= !vis[i];
    }

    assert(false);
}

int getIdxB(int node)
{
    int idx = 0;
    for (int i = 0 ; i <= node ; ++i)
    {
        idx += !vis[i];
    }

    return idx;
}

std::pair <int,int> readPairB()
{
    if (receivedQueue.front() == 1)
    {
        receivedQueue.pop();
        return {n + 1, 1e9};
    }

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

void ReceiveB(bool x) 
{
    while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
    {
        NODE_BITS--;
    }

    receivedQueue.push(x);
    if (cntEntries == cntDoneTurns && sequence[cntEntries])
    {
        receivedQueue.pop();
        manageB();
        return;
    }

    if (receivedQueue.size() == NODE_BITS + DIST_BITS + 1 || (receivedQueue.size() == 1 && receivedQueue.front() == 1))
    {
        if (sequence[cntDoneTurns] == 1) receiveSendPairB();
        else receiveResendPairB();
    }
}

void sendMyTopB()
{
    cntEntries++;
    while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
    {
        NODE_BITS--;
    }

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

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

    if (otherNode < n) pq.push({otherNode, otherDist});
    while (pq.size() && vis[pq.top().node])
    {
        pq.pop();
    }

    if (pq.size())
    {
        // std::cout << "hereAAA: " << pq.top().currDist << ' ' << lastDist << '\n';
        // std::cout << "topA: " << pq.top().node << ' ' << 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();
    }

    cntDoneTurns++;
    if (cntDoneTurns < n && sequence[cntDoneTurns] == 0)
    {
        SendB(0);
    }
}

void receiveResendPairB()
{   
    while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
    {
        NODE_BITS--;
    }

    cntEntries++;
    auto [otherNode, otherDist] = readPairB();
    otherNode = getNodeB(otherNode);
    otherDist += lastDist;
    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;
    
    PQelement other = {otherNode, otherDist};
    // if (pq.size()) std::cout << "try b: " << pq.top().node << ' ' << pq.top().currDist << '\n';
    if (pq.size() && (otherNode >= n || other < pq.top()))
    {
        // std::cout << "send from B: " << pq.top().node << ' ' << pq.top().currDist << ' ' << lastDist << ' ' << vis[pq.top().node] << ' ' << getIdxB(pq.top().node) << ' ' << n - cntDoneTurns << '\n';
        SendB(0);
        writeB(getIdxB(pq.top().node), NODE_BITS);
        writeB(pq.top().currDist - lastDist, DIST_BITS);
    } else if (pq.size())
    {
        SendB(1);
    }

    if (pq.size())
    {
        auto [node, currDist] = pq.top();
        // 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]});
            }
        }
    }

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

    cntDoneTurns++;
    if (cntDoneTurns < n && sequence[cntDoneTurns] == 0)
    {
        SendB(0);
    }
}

void manageB()
{
    sendMyTopB();
}

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

    while (sequence.size() < n)
    {
        sequence.push_back(rng() % 2);
    }

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

Compilation message (stderr)

Azer.cpp: In function 'void sendMyTopA()':
Azer.cpp:94:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   94 |     while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
      |                                   ~~~~~~~~~~^~~
Azer.cpp: In function 'void receiveResendPairA()':
Azer.cpp:159:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  159 |     while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
      |                                   ~~~~~~~~~~^~~
Azer.cpp:175:10: warning: unused variable 'whatShouldSend' [-Wunused-variable]
  175 |     bool whatShouldSend = false;
      |          ^~~~~~~~~~~~~~
Azer.cpp: In function 'void ReceiveA(bool)':
Azer.cpp:225:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  225 |     while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
      |                                   ~~~~~~~~~~^~~
Azer.cpp:238:30: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  238 |     if (receivedQueue.size() == NODE_BITS + DIST_BITS + 1 || (receivedQueue.size() == 1 && receivedQueue.front() == 1))
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:281:28: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  281 |     while (sequence.size() < n)
      |            ~~~~~~~~~~~~~~~~^~~

Baijan.cpp: In function 'void ReceiveB(bool)':
Baijan.cpp:92:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
   92 |     while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
      |                                   ~~~~~~~~~~^~~
Baijan.cpp:105:30: warning: comparison of integer expressions of different signedness: 'std::queue<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  105 |     if (receivedQueue.size() == NODE_BITS + DIST_BITS + 1 || (receivedQueue.size() == 1 && receivedQueue.front() == 1))
      |         ~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
Baijan.cpp: In function 'void sendMyTopB()':
Baijan.cpp:115:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  115 |     while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
      |                                   ~~~~~~~~~~^~~
Baijan.cpp: In function 'void receiveResendPairB()':
Baijan.cpp:180:45: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
  180 |     while (NODE_BITS > 1 && (1 << NODE_BITS - 1) > n - cntDoneTurns)
      |                                   ~~~~~~~~~~^~~
Baijan.cpp:196:10: warning: unused variable 'whatShouldSend' [-Wunused-variable]
  196 |     bool whatShouldSend = false;
      |          ^~~~~~~~~~~~~~
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:280:28: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  280 |     while (sequence.size() < n)
      |            ~~~~~~~~~~~~~~~~^~~

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