제출 #318949

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
318949		admin	Two Transportations (JOI19_transportations)	C++17	0 / 100	2 ms	580 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 %d-th 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]) {
                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: 0 / 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