Submission #1189712

#	Time	Username	Problem	Language	Result	Execution time	Memory
1189712		oviyan_gandhi	Two Transportations (JOI19_transportations)	C++20	38 / 100	255 ms	35912 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

const int INF = 10000000, NX = (1 << 11) - 1;
typedef pair<int, int> pii;

int ctr = 0, n1 = 0, n2 = 0, ans = INF; // n1 is 11 bits (vertex), n2 is 20 bits (distance)

vector<int> dist;
vector<vector<pii>> adj;
priority_queue<pii, vector<pii>, greater<pii>> pq;

void send(int x, int y) {
    for (int i = 0; i < 11; i++)
        SendA(x & (1 << i));
    for (int i = 0; i < 20; i++)
        SendA(y & (1 << i));
}

void receive(int x, int y) { // x = node, y = dist
    if (x != NX && y < dist[x]) {
        dist[x] = y;
        pq.push({dist[x], x});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
        break;
    }
    while (!pq.empty() && pq.top().first > dist[pq.top().second])
        pq.pop();
    if (pq.empty()) {
        if (x == NX) Answer();
        else send(NX, 0);
    }
    else
        send(pq.top().second, pq.top().first);
}

}  // namespace

void InitA(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
    adj.resize(N);
    for (int i = 0; i < A; i++) {
        adj[U[i]].push_back({V[i], C[i]});
        adj[V[i]].push_back({U[i], C[i]});
    }
    dist.assign(N, INF);
    dist[0] = 0;
    pq.push({0, 0});
    send(0, 0);
}

void ReceiveA(bool x) {
    if (ctr > 10)
        n2 += x*(1 << (ctr-11));
    else
        n1 += x*(1 << ctr);
    if (++ctr == 31) {
        ctr = 0;
        receive(n1, n2);
        n1 = n2 = 0;
    }
}

vector<int> Answer() {
    return dist;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;

namespace {

const int INF = 10000000, NX = (1 << 11) - 1;
typedef pair<int, int> pii;

int ctr = 0, n1 = 0, n2 = 0; // n1 is 11 bits (vertex), n2 is 20 bits (distance)

vector<int> dist;
vector<vector<pii>> adj;
priority_queue<pii, vector<pii>, greater<pii>> pq;

void send(int x, int y) {
    for (int i = 0; i < 11; i++)
        SendB(x & (1 << i));
    for (int i = 0; i < 20; i++)
        SendB(y & (1 << i));
}

void receive(int x, int y) { // x = node, y = dist
    if (x != NX && y < dist[x]) {
        dist[x] = y;
        pq.push({dist[x], x});
    }
    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();
        if (d > dist[u]) continue;
        for (auto [v, w] : adj[u]) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                pq.push({dist[v], v});
            }
        }
        break;
    }
    while (!pq.empty() && pq.top().first > dist[pq.top().second])
        pq.pop();
    if (pq.empty())
        send(NX, 0);
    else
        send(pq.top().second, pq.top().first);
}

}  // namespace

void InitB(int N, int B, vector<int> S, vector<int> T, vector<int> D) {
    adj.resize(N);
    for (int i = 0; i < B; i++) {
        adj[S[i]].push_back({T[i], D[i]});
        adj[T[i]].push_back({S[i], D[i]});
    }
    dist.assign(N, INF);
    dist[0] = 0;
    pq.push({0, 0});
}

void ReceiveB(bool y) {
    if (ctr > 10)
        n2 += y*(1 << (ctr-11));
    else
        n1 += y*(1 << ctr);
    if (++ctr == 31) {
        ctr = 0;
        receive(n1, n2);
        n1 = n2 = 0;
    }
}

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