oj.uz

답안 #927965

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927965 2024-02-15T15:16:45 Z boris_mihov Two Transportations (JOI19_transportations) C++17
68 / 100
 422 ms 49092 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 cntDoneTurns;
static int cntEntries;

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

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

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

void sendMyTopA()
{
    cntEntries++;
    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
    {
        // std::cout << "send from A: " << n << ' ' << -1 << '\n';
        SendA(1);
    }
}

void receiveSendPairA()
{   
    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();
    }

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

void receiveResendPairA()
{   
    cntEntries++;
    auto [otherNode, otherDist] = readPairA();
    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(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) 
{
    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() & 1);
    }

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

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

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

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

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

Compilation message

Azer.cpp: In function 'void receiveResendPairA()':
Azer.cpp:129:10: warning: unused variable 'whatShouldSend' [-Wunused-variable]
  129 |     bool whatShouldSend = false;
      |          ^~~~~~~~~~~~~~
Azer.cpp: In function 'void InitA(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Azer.cpp:230:28: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  230 |     while (sequence.size() < n)
      |            ~~~~~~~~~~~~~~~~^~~

Baijan.cpp: In function 'void receiveResendPairB()':
Baijan.cpp:148:10: warning: unused variable 'whatShouldSend' [-Wunused-variable]
  148 |     bool whatShouldSend = false;
      |          ^~~~~~~~~~~~~~
Baijan.cpp: In function 'void InitB(int, int, std::vector<int>, std::vector<int>, std::vector<int>)':
Baijan.cpp:232:28: warning: comparison of integer expressions of different signedness: 'std::vector<bool>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  232 |     while (sequence.size() < n)
      |            ~~~~~~~~~~~~~~~~^~~

Subtask #1
6.0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 1056 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 223 ms 1056 KB Output is correct
4 Correct 306 ms 10380 KB Output is correct
5 Correct 10 ms 920 KB Output is correct
6 Correct 239 ms 2468 KB Output is correct

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 664 KB Output is correct
2 Correct 220 ms 892 KB Output is correct
3 Correct 276 ms 944 KB Output is correct
4 Runtime error 222 ms 27328 KB Execution killed with signal 13
5 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 127 ms 540 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 832 KB Output is correct
2 Correct 128 ms 820 KB Output is correct
3 Correct 162 ms 13472 KB Output is correct
4 Correct 148 ms 664 KB Output is correct
5 Correct 156 ms 10076 KB Output is correct
6 Correct 82 ms 836 KB Output is correct
7 Correct 135 ms 868 KB Output is correct
8 Correct 133 ms 868 KB Output is correct
9 Correct 179 ms 18492 KB Output is correct
10 Correct 184 ms 18624 KB Output is correct
11 Correct 303 ms 35820 KB Output is correct
12 Correct 279 ms 31288 KB Output is correct
13 Correct 137 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct

Subtask #5
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 832 KB Output is correct
2 Correct 128 ms 820 KB Output is correct
3 Correct 162 ms 13472 KB Output is correct
4 Correct 148 ms 664 KB Output is correct
5 Correct 156 ms 10076 KB Output is correct
6 Correct 82 ms 836 KB Output is correct
7 Correct 135 ms 868 KB Output is correct
8 Correct 133 ms 868 KB Output is correct
9 Correct 179 ms 18492 KB Output is correct
10 Correct 184 ms 18624 KB Output is correct
11 Correct 303 ms 35820 KB Output is correct
12 Correct 279 ms 31288 KB Output is correct
13 Correct 137 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Correct 155 ms 836 KB Output is correct
16 Correct 155 ms 920 KB Output is correct
17 Correct 108 ms 916 KB Output is correct
18 Correct 207 ms 10284 KB Output is correct
19 Correct 177 ms 664 KB Output is correct
20 Correct 181 ms 10692 KB Output is correct
21 Correct 160 ms 664 KB Output is correct
22 Correct 157 ms 664 KB Output is correct
23 Correct 238 ms 22436 KB Output is correct
24 Correct 229 ms 22548 KB Output is correct
25 Correct 372 ms 43688 KB Output is correct
26 Correct 351 ms 36816 KB Output is correct
27 Correct 165 ms 900 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 103 ms 832 KB Output is correct
2 Correct 128 ms 820 KB Output is correct
3 Correct 162 ms 13472 KB Output is correct
4 Correct 148 ms 664 KB Output is correct
5 Correct 156 ms 10076 KB Output is correct
6 Correct 82 ms 836 KB Output is correct
7 Correct 135 ms 868 KB Output is correct
8 Correct 133 ms 868 KB Output is correct
9 Correct 179 ms 18492 KB Output is correct
10 Correct 184 ms 18624 KB Output is correct
11 Correct 303 ms 35820 KB Output is correct
12 Correct 279 ms 31288 KB Output is correct
13 Correct 137 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Correct 155 ms 836 KB Output is correct
16 Correct 155 ms 920 KB Output is correct
17 Correct 108 ms 916 KB Output is correct
18 Correct 207 ms 10284 KB Output is correct
19 Correct 177 ms 664 KB Output is correct
20 Correct 181 ms 10692 KB Output is correct
21 Correct 160 ms 664 KB Output is correct
22 Correct 157 ms 664 KB Output is correct
23 Correct 238 ms 22436 KB Output is correct
24 Correct 229 ms 22548 KB Output is correct
25 Correct 372 ms 43688 KB Output is correct
26 Correct 351 ms 36816 KB Output is correct
27 Correct 165 ms 900 KB Output is correct
28 Correct 208 ms 664 KB Output is correct
29 Correct 210 ms 800 KB Output is correct
30 Correct 267 ms 24236 KB Output is correct
31 Correct 142 ms 808 KB Output is correct
32 Correct 262 ms 21384 KB Output is correct
33 Correct 217 ms 872 KB Output is correct
34 Correct 180 ms 1176 KB Output is correct
35 Correct 210 ms 920 KB Output is correct
36 Correct 277 ms 24984 KB Output is correct
37 Correct 281 ms 24988 KB Output is correct
38 Correct 422 ms 49092 KB Output is correct
39 Correct 400 ms 44136 KB Output is correct
40 Correct 194 ms 1176 KB Output is correct

Subtask #7
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 234 ms 1056 KB Output is correct
2 Correct 0 ms 664 KB Output is correct
3 Correct 223 ms 1056 KB Output is correct
4 Correct 306 ms 10380 KB Output is correct
5 Correct 10 ms 920 KB Output is correct
6 Correct 239 ms 2468 KB Output is correct
7 Correct 0 ms 664 KB Output is correct
8 Correct 220 ms 892 KB Output is correct
9 Correct 276 ms 944 KB Output is correct
10 Runtime error 222 ms 27328 KB Execution killed with signal 13
11 Halted 0 ms 0 KB -