oj.uz

답안 #927840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927840 2024-02-15T11:43:40 Z boris_mihov Two Transportations (JOI19_transportations) C++17
62 / 100
 534 ms 49036 KB 
#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;
    }
};

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

void receivePairA()
{   
    int otherNode = readA(NODE_BITS);
    int otherDist = lastDist + readA(DIST_BITS);
    // std::cout << "receive from B: " << otherNode << ' ' << otherDist << '\n';
    if (otherNode != n) pq.push({otherNode, otherDist});

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

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

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

    if (pq.size())
    {
        // std::cout << "pqB size\n";
        auto [node, currDist] = pq.top();
        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]});
    }

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

Subtask #1
0 / 6.0

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

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 664 KB Output is correct
2 Runtime error 151 ms 548 KB Execution killed with signal 13
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
38.0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 820 KB Output is correct
2 Correct 165 ms 808 KB Output is correct
3 Correct 252 ms 13460 KB Output is correct
4 Correct 160 ms 676 KB Output is correct
5 Correct 187 ms 10100 KB Output is correct
6 Correct 182 ms 664 KB Output is correct
7 Correct 165 ms 1116 KB Output is correct
8 Correct 212 ms 664 KB Output is correct
9 Correct 275 ms 18372 KB Output is correct
10 Correct 333 ms 18476 KB Output is correct
11 Correct 388 ms 35792 KB Output is correct
12 Correct 338 ms 31028 KB Output is correct
13 Correct 243 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 175 ms 820 KB Output is correct
2 Correct 165 ms 808 KB Output is correct
3 Correct 252 ms 13460 KB Output is correct
4 Correct 160 ms 676 KB Output is correct
5 Correct 187 ms 10100 KB Output is correct
6 Correct 182 ms 664 KB Output is correct
7 Correct 165 ms 1116 KB Output is correct
8 Correct 212 ms 664 KB Output is correct
9 Correct 275 ms 18372 KB Output is correct
10 Correct 333 ms 18476 KB Output is correct
11 Correct 388 ms 35792 KB Output is correct
12 Correct 338 ms 31028 KB Output is correct
13 Correct 243 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Correct 225 ms 828 KB Output is correct
16 Correct 198 ms 668 KB Output is correct
17 Correct 276 ms 664 KB Output is correct
18 Correct 309 ms 10440 KB Output is correct
19 Correct 267 ms 664 KB Output is correct
20 Correct 326 ms 10680 KB Output is correct
21 Correct 274 ms 664 KB Output is correct
22 Correct 242 ms 664 KB Output is correct
23 Correct 368 ms 22416 KB Output is correct
24 Correct 381 ms 22588 KB Output is correct
25 Correct 439 ms 44028 KB Output is correct
26 Correct 380 ms 36932 KB Output is correct
27 Correct 225 ms 888 KB Output is correct

Subtask #6
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 175 ms 820 KB Output is correct
2 Correct 165 ms 808 KB Output is correct
3 Correct 252 ms 13460 KB Output is correct
4 Correct 160 ms 676 KB Output is correct
5 Correct 187 ms 10100 KB Output is correct
6 Correct 182 ms 664 KB Output is correct
7 Correct 165 ms 1116 KB Output is correct
8 Correct 212 ms 664 KB Output is correct
9 Correct 275 ms 18372 KB Output is correct
10 Correct 333 ms 18476 KB Output is correct
11 Correct 388 ms 35792 KB Output is correct
12 Correct 338 ms 31028 KB Output is correct
13 Correct 243 ms 664 KB Output is correct
14 Correct 0 ms 664 KB Output is correct
15 Correct 225 ms 828 KB Output is correct
16 Correct 198 ms 668 KB Output is correct
17 Correct 276 ms 664 KB Output is correct
18 Correct 309 ms 10440 KB Output is correct
19 Correct 267 ms 664 KB Output is correct
20 Correct 326 ms 10680 KB Output is correct
21 Correct 274 ms 664 KB Output is correct
22 Correct 242 ms 664 KB Output is correct
23 Correct 368 ms 22416 KB Output is correct
24 Correct 381 ms 22588 KB Output is correct
25 Correct 439 ms 44028 KB Output is correct
26 Correct 380 ms 36932 KB Output is correct
27 Correct 225 ms 888 KB Output is correct
28 Correct 318 ms 664 KB Output is correct
29 Correct 244 ms 804 KB Output is correct
30 Correct 454 ms 24360 KB Output is correct
31 Correct 356 ms 788 KB Output is correct
32 Correct 414 ms 21248 KB Output is correct
33 Correct 282 ms 868 KB Output is correct
34 Correct 266 ms 896 KB Output is correct
35 Correct 267 ms 896 KB Output is correct
36 Correct 418 ms 25100 KB Output is correct
37 Correct 412 ms 25188 KB Output is correct
38 Correct 534 ms 49036 KB Output is correct
39 Correct 485 ms 44348 KB Output is correct
40 Correct 252 ms 1176 KB Output is correct

Subtask #7
0 / 16.0

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