oj.uz

답안 #927838

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
927838 2024-02-15T11:41:33 Z boris_mihov Two Transportations (JOI19_transportations) C++17
0 / 100
 225 ms 13704 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';
    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() && pq.top().node != n)
    {
        // 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() && pq.top().node != n)
    {
        // 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 176 ms 460 KB Execution killed with signal 13
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 664 KB Output is correct
2 Incorrect 2 ms 908 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 8.0

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

Subtask #4
0 / 38.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 824 KB Output is correct
2 Correct 184 ms 812 KB Output is correct
3 Correct 225 ms 13704 KB Output is correct
4 Correct 173 ms 852 KB Output is correct
5 Correct 221 ms 10108 KB Output is correct
6 Incorrect 2 ms 920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #5
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 824 KB Output is correct
2 Correct 184 ms 812 KB Output is correct
3 Correct 225 ms 13704 KB Output is correct
4 Correct 173 ms 852 KB Output is correct
5 Correct 221 ms 10108 KB Output is correct
6 Incorrect 2 ms 920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 207 ms 824 KB Output is correct
2 Correct 184 ms 812 KB Output is correct
3 Correct 225 ms 13704 KB Output is correct
4 Correct 173 ms 852 KB Output is correct
5 Correct 221 ms 10108 KB Output is correct
6 Incorrect 2 ms 920 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #7
0 / 16.0

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