oj.uz

Submission #927963

# Submission time Handle Problem Language Result Execution time Memory
927963 2024-02-15T14:56:07 Z boris_mihov Two Transportations (JOI19_transportations) C++17
66 / 100
 405 ms 43680 KB 
#include "Azer.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <random>
#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::mt19937 rng(69420);
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 cntEntries;

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

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

void receivePairA()
{   
    auto [otherNode, otherDist] = readPairA();
    // 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();
    }

    if (pq.size())
    {
        // std::cout << "send from A: " << pq.top().node << ' ' << pq.top().currDist << '\n';
        SendA(0);
        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';
        SendA(1);
    }
}

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

    while (sequence.size() < n)
    {
        sequence.push_back(rng() & 1);
    }

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

    SendA(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;
}

#include "Baijan.h"
#include <algorithm>
#include <iostream>
#include <numeric>
#include <cassert>
#include <cassert>
#include <random>
#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];
static std::mt19937 rng(69420);
static std::vector <bool> sequence;
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 receivePairB();

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

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

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

void receivePairB()
{   
    auto [otherNode, otherDist] = readPairB();
    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';
        SendB(0);
        writeB(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();
    }
}

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() & 1);
    }

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

Compilation message

Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:144:28: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  144 |     while (sequence.size() < n)
      |            ~~~~~~~~~~~~~~~~^~~
Azer.cpp: At global scope:
Azer.cpp:38:12: warning: 'cntEntries' defined but not used [-Wunused-variable]
   38 | static int cntEntries;
      |            ^~~~~~~~~~

Baijan.cpp: In function 'void receivePairB()':
Baijan.cpp:76:10: warning: unused variable 'whatShouldSend' [-Wunused-variable]
   76 |     bool whatShouldSend = false;
      |          ^~~~~~~~~~~~~~
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:149:28: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  149 |     while (sequence.size() < n)
      |            ~~~~~~~~~~~~~~~~^~~
Baijan.cpp: At global scope:
Baijan.cpp:24:12: warning: 'cntEntries' defined but not used [-Wunused-variable]
   24 | static int cntEntries;
      |            ^~~~~~~~~~

Subtask #1
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 1056 KB Output is correct
2 Correct 0 ms 832 KB Output is correct
3 Correct 210 ms 1052 KB Output is correct
4 Correct 299 ms 10380 KB Output is correct
5 Correct 13 ms 920 KB Output is correct
6 Correct 213 ms 2472 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 664 KB Output is correct
2 Correct 231 ms 884 KB Output is correct
3 Correct 255 ms 944 KB Output is correct
4 Correct 351 ms 27720 KB Output is correct
5 Correct 370 ms 24524 KB Output is correct
6 Correct 39 ms 808 KB Output is correct
7 Correct 355 ms 24612 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 98 ms 540 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 664 KB Output is correct
2 Correct 167 ms 816 KB Output is correct
3 Correct 144 ms 13460 KB Output is correct
4 Correct 168 ms 664 KB Output is correct
5 Correct 175 ms 10080 KB Output is correct
6 Correct 94 ms 836 KB Output is correct
7 Correct 138 ms 664 KB Output is correct
8 Correct 125 ms 844 KB Output is correct
9 Correct 192 ms 18492 KB Output is correct
10 Correct 194 ms 18496 KB Output is correct
11 Correct 330 ms 35728 KB Output is correct
12 Correct 288 ms 31100 KB Output is correct
13 Correct 124 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct

Subtask #5
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 664 KB Output is correct
2 Correct 167 ms 816 KB Output is correct
3 Correct 144 ms 13460 KB Output is correct
4 Correct 168 ms 664 KB Output is correct
5 Correct 175 ms 10080 KB Output is correct
6 Correct 94 ms 836 KB Output is correct
7 Correct 138 ms 664 KB Output is correct
8 Correct 125 ms 844 KB Output is correct
9 Correct 192 ms 18492 KB Output is correct
10 Correct 194 ms 18496 KB Output is correct
11 Correct 330 ms 35728 KB Output is correct
12 Correct 288 ms 31100 KB Output is correct
13 Correct 124 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Correct 160 ms 840 KB Output is correct
16 Correct 109 ms 920 KB Output is correct
17 Correct 107 ms 856 KB Output is correct
18 Correct 175 ms 10220 KB Output is correct
19 Correct 165 ms 664 KB Output is correct
20 Correct 200 ms 10496 KB Output is correct
21 Correct 162 ms 664 KB Output is correct
22 Correct 157 ms 664 KB Output is correct
23 Correct 249 ms 22232 KB Output is correct
24 Correct 229 ms 22436 KB Output is correct
25 Correct 405 ms 43680 KB Output is correct
26 Correct 310 ms 36812 KB Output is correct
27 Correct 152 ms 664 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 152 ms 664 KB Output is correct
2 Correct 167 ms 816 KB Output is correct
3 Correct 144 ms 13460 KB Output is correct
4 Correct 168 ms 664 KB Output is correct
5 Correct 175 ms 10080 KB Output is correct
6 Correct 94 ms 836 KB Output is correct
7 Correct 138 ms 664 KB Output is correct
8 Correct 125 ms 844 KB Output is correct
9 Correct 192 ms 18492 KB Output is correct
10 Correct 194 ms 18496 KB Output is correct
11 Correct 330 ms 35728 KB Output is correct
12 Correct 288 ms 31100 KB Output is correct
13 Correct 124 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Correct 160 ms 840 KB Output is correct
16 Correct 109 ms 920 KB Output is correct
17 Correct 107 ms 856 KB Output is correct
18 Correct 175 ms 10220 KB Output is correct
19 Correct 165 ms 664 KB Output is correct
20 Correct 200 ms 10496 KB Output is correct
21 Correct 162 ms 664 KB Output is correct
22 Correct 157 ms 664 KB Output is correct
23 Correct 249 ms 22232 KB Output is correct
24 Correct 229 ms 22436 KB Output is correct
25 Correct 405 ms 43680 KB Output is correct
26 Correct 310 ms 36812 KB Output is correct
27 Correct 152 ms 664 KB Output is correct
28 Correct 200 ms 664 KB Output is correct
29 Runtime error 140 ms 472 KB Execution killed with signal 13
30 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 261 ms 1056 KB Output is correct
2 Correct 0 ms 832 KB Output is correct
3 Correct 210 ms 1052 KB Output is correct
4 Correct 299 ms 10380 KB Output is correct
5 Correct 13 ms 920 KB Output is correct
6 Correct 213 ms 2472 KB Output is correct
7 Correct 2 ms 664 KB Output is correct
8 Correct 231 ms 884 KB Output is correct
9 Correct 255 ms 944 KB Output is correct
10 Correct 351 ms 27720 KB Output is correct
11 Correct 370 ms 24524 KB Output is correct
12 Correct 39 ms 808 KB Output is correct
13 Correct 355 ms 24612 KB Output is correct
14 Runtime error 98 ms 540 KB Execution killed with signal 13
15 Halted 0 ms 0 KB -