Submission #296558

#	Time	Username	Problem	Language	Result	Execution time	Memory
296558		matt_H	Two Transportations (JOI19_transportations)	C++14	6 / 100	1138 ms	20256 KiB

Azer

#include "Azer.h"
#include <cstdio>
#include <vector>
#include <queue>

typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector<pii> vii;
typedef std::vector<vii> vvii;

namespace {
    int N, done;
    vi dist, alive;
    vvii neighbors;
    std::priority_queue<pii> dijkQ;
    const int INF = 1000000000;
    const int INF_W = 511;

    int reg;
    int other_dist, cur_dist;
    int expected, cnt;
    enum Event { receivedDist, receivedPoint } event;
    void receiveInt(int n, Event e) {
        expected = n;
        cnt = 0;
        reg = 0;
        event = e;
    }

    void sendInt(int n, int to_send) {
        for (int i = 0; i < n; i++) {
            SendA(to_send & 1);
            to_send >>= 1;
        }
    }

    pii peek(std::priority_queue<pii> &q) {
        if (q.empty())
            return {INF_W, -1};
        pii rst;
        rst = q.top();
        while (!alive[rst.second]) {
            q.pop();
            if (q.empty())
                return {INF_W, -1};
            rst = q.top();
        }
        return {(-rst.first) - cur_dist, rst.second};
    }

    pii holding;

    void dijk_step() {
        // holding is the to-be-expanded node
        cur_dist += holding.first;
        int cur_node = holding.second;
        dist[cur_node] = cur_dist;
        done++;
        alive[cur_node] = false;
//        fprintf(stderr, "Alice does dijk on %d with dist %d\n", cur_node, cur_dist);

        if (done == N)
            return;

        for (auto it : neighbors[cur_node])
            if (alive[it.second] && cur_dist + it.first < dist[it.second]) {
                dist[it.second] = cur_dist + it.first;
                dijkQ.emplace(-(cur_dist + it.first), it.second);
            }

        holding = peek(dijkQ);

        sendInt(9, holding.first);
        receiveInt(9, receivedDist);
    }

    void compare_with_other() {
        other_dist = reg;
//        fprintf(stderr, "Alice compare her %d on node %d from Bob's dist %d\n",
//                holding.first, holding.second, other_dist);
        if (other_dist < holding.first)
            receiveInt(11, receivedPoint);
        else {
            sendInt(11, holding.second);
            dijk_step();
        }
    }

    void envoke_handler() {
       switch(event) {
           case receivedDist:
               compare_with_other();
               break;
           case receivedPoint:
//               fprintf(stderr, "Alice received from Bob the point %d\n", reg);
               holding.first = other_dist;
               holding.second = reg;
               dijk_step();
       }
    }

}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
    ::N = N;
    done = 0;
    neighbors.assign(N, vii());
    dist.assign(N, INF);
    alive.assign(N, true);
    for (int i = 0; i < A; i++) {
        neighbors[U[i]].emplace_back(C[i], V[i]);
        neighbors[V[i]].emplace_back(C[i], U[i]);
    }

    holding.first = holding.second = 0;
    cur_dist = 0;
    dijk_step();
}

void ReceiveA(bool x) {
    expected--;
    if (expected < 0)
        fprintf(stderr, "unexpected msg from B.");
    else {
        // this is the cnt-th bit received
        reg |= (x << cnt);
    }
    cnt++;
    if (expected == 0) // transferred fin
        envoke_handler();
}

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

Baijan

#include "Baijan.h"
#include <cstdio>
#include <vector>
#include <queue>

typedef std::pair<int, int> pii;
typedef std::vector<int> vi;
typedef std::vector<pii> vii;
typedef std::vector<vii> vvii;

namespace {
    int N, done;
    vi dist, alive;
    vvii neighbors;
    std::priority_queue<pii> dijkQ;
    const int INF = 1000000000;
    const int INF_W = 511;

    int reg;
    int other_dist, cur_dist;
    int expected, cnt;
    enum Event { receivedDist, receivedPoint } event;
    void receiveInt(int n, Event e) {
        expected = n;
        cnt = 0;
        reg = 0;
        event = e;
    }

    void sendInt(int n, int to_send) {
        for (int i = 0; i < n; i++) {
            SendB(to_send & 1);
            to_send >>= 1;
        }
    }

    pii peek(std::priority_queue<pii> &q) {
        if (q.empty())
            return {INF_W, -1};
        pii rst;
        rst = q.top();
        while (!alive[rst.second]) {
            q.pop();
            if (q.empty())
                return {INF_W, -1};
            rst = q.top();
        }
        return {(-rst.first) - cur_dist, rst.second};
    }

    pii holding;

    void dijk_step() {
        // holding is the to-be-expanded node
        cur_dist += holding.first;
        int cur_node = holding.second;
        dist[cur_node] = cur_dist;
        done++;
        alive[cur_node] = false;
//        fprintf(stderr, "%d-th iteration Bob does dijk on %d with dist %d\n", done, cur_node, cur_dist);

        if (done == N)
            return;

        for (auto it : neighbors[cur_node])
            if (alive[it.second] && cur_dist + it.first < dist[it.second]) {
//                fprintf(stderr, "Bob updating %d to %d\n", it.second, cur_dist + it.first);
                dist[it.second] = cur_dist + it.first;
                dijkQ.emplace(-(cur_dist + it.first), it.second);
            }

        holding = peek(dijkQ);
        sendInt(9, holding.first);
        receiveInt(9, receivedDist);

    }

    void compare_with_other() {
        other_dist = reg;
//        fprintf(stderr, "Bob compare his %d on node %d from Alice's dist %d\n",
//                holding.first, holding.second, other_dist);
        if (other_dist < holding.first)
            receiveInt(11, receivedPoint);
        else {
            sendInt(11, holding.second);
            dijk_step();
        }
    }

    void envoke_handler() {
        switch(event) {
            case receivedDist:
                compare_with_other();
                break;
            case receivedPoint:
                holding.first = other_dist;
                holding.second = reg;
                dijk_step();
        }
    }

}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
    ::N = N;
    done = 0;
    neighbors.assign(N, vii());
    dist.assign(N, INF);
    alive.assign(N, true);
    for (int i = 0; i < B; i++) {
        neighbors[S[i]].emplace_back(D[i], T[i]);
        neighbors[T[i]].emplace_back(D[i], S[i]);
    }

    holding.first = holding.second = 0;
    cur_dist = 0;
    dijk_step();
}

void ReceiveB(bool x) {
    expected--;
    if (expected < 0)
        fprintf(stderr, "unexpected msg from A.");
    else {
        // this is the cnt-th bit received
        reg |= (x << cnt);
    }
    cnt++;
    if (expected == 0) // transferred fin
        envoke_handler();
}

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