제출 #927833

#제출 시각아이디문제언어결과실행 시간메모리
927833boris_mihovTwo Transportations (JOI19_transportations)C++17
0 / 100
271 ms13580 KiB
#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()) { if (pq.top().node == n) { return; } // std::cout << "hereAAA: " << pq.top().currDist << ' ' << lastDist << '\n'; if (pq.top().currDist - lastDist == 501) { return; } 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 { // std::cout << "send from A: " << n << ' ' << -1 << '\n'; writeA(n, NODE_BITS); writeA(501, 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(501, 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()) { // std::cout << "pqB size\n"; if (pq.top().node == n) { // std::cout << " good return\n"; return; } 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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...