# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
927944 | 2024-02-15T14:27:30 Z | boris_mihov | Two Transportations (JOI19_transportations) | C++17 | 0 ms | 0 KB |
#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 || (a.currDist == b.currDist && a.node > b.node); } }; 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 (otherNode < n) pq.push({otherNode, otherDist}); // std::cout << "from A: " << otherNode << ' ' << otherDist - lastDist << '\n'; while (pq.size() && vis[pq.top().node]) { pq.pop(); } bool whatShouldSend = false; bool isEmpty = true; if (pq.size() && (otherNode >= n || pq.top().currDist < otherDist)) { // std::cout << "send from B: " << pq.top().node << ' ' << pq.top().currDist << ' ' << lastDist << '\n'; SendB(0); writeB(pq.top().node, NODE_BITS); writeB(pq.top().currDist - lastDist, DIST_BITS); } else if (otherNode != n) { whatShouldSend = true; } if (pq.size()) { auto [node, currDist] = pq.top(); isEmpty = false; // std::cout << "topB: " << node << ' ' << currDist << "\n"; 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]}); } } } if (whatShouldSend) { if (pq.size() || !isEmpty) SendB(1); else { SendB(0); writeB(n + 1, NODE_BITS); writeB(lastDist, DIST_BITS); } } 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; }