제출 #915874

#제출 시각아이디문제언어결과실행 시간메모리
915874gawr_guraTwo Transportations (JOI19_transportations)C++17
14 / 100
489 ms27884 KiB
#include "Azer.h" #include <bits/stdc++.h> using namespace std; namespace a { int N; vector<vector<pair<int, int>>> adj; priority_queue<pair<int, int>> pq; vector<int> d; vector<int> done; int max_until_now = 0; bool receive_length = 0; int cnt_length; int length, length_a; int pos, cnt_pos; int a; void send_nude(int du, int u) { // cerr << du << ' ' << u << '\n'; length_a = du - max_until_now; a = u; // cerr << "now sending length " << length_a << " from a to b!\n"; for (int i = 0; i < 9; i++) SendA(length_a >> i & 1); receive_length = 1; cnt_length = length = 0; } void try_next() { while (pq.size()) { auto [du, u] = pq.top(); // cerr << "pq : " << du << ' ' << u << '\n'; if (done[u] == 0) { send_nude(-du, u); return; } pq.pop(); // cerr << d[u] << '\n'; if (-du != d[u]) continue; max_until_now = -du; for (auto [v, w] : adj[u]) { if (d[v] > d[u] + w) { d[v] = d[u] + w; pq.emplace(-d[v], v); } } } send_nude(max_until_now + 511, 0); } } // namespace a void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) { a::N = N; a::adj.resize(N); a::d.assign(N, 1e9); a::done.assign(N, 0); for (int i = 0; i < A; i++) a::adj[U[i]].emplace_back(V[i], C[i]); for (int i = 0; i < A; i++) a::adj[V[i]].emplace_back(U[i], C[i]); a::pq.emplace(0, 0); a::d[0] = 0; a::done[0] = 1; a::try_next(); } void ReceiveA(bool x) { if (a::receive_length) { a::length |= x << a::cnt_length; a::cnt_length++; if (a::cnt_length == 9) { // cerr << "now receiving length " << a::length << " from b to a\n"; if (a::length < a::length_a) { a::length += a::max_until_now; a::pos = a::cnt_pos = 0; a::receive_length = 0; } else { // cerr << "now sending pos " << a::a << " from a to b!\n"; for (int i = 0; i < 11; i++) SendA(a::a >> i & 1); a::done[a::a] = 1; a::try_next(); } } } else { a::pos |= x << a::cnt_pos; a::cnt_pos++; if (a::cnt_pos == 11) { // cerr << a::max_until_now << '\n'; // cerr << "now receiving pos " << a::pos << " from b to a!\n"; a::done[a::pos] = 1; a::d[a::pos] = a::length; a::pq.emplace(-a::length, a::pos); a::try_next(); } } } std::vector<int> Answer() { return a::d; }
#include "Baijan.h" #include <bits/stdc++.h> using namespace std; namespace b { int N; int x = 0; vector<vector<pair<int, int>>> adj; priority_queue<pair<int, int>> pq; vector<int> d; vector<int> done; int length, cnt_length; bool receive_length; int length_b; int max_until_now; int pos, cnt_pos; void send_nude(int du, int u) { // cerr << "send_nude on b: " << du << ' ' << u << '\n'; int length_b = du - max_until_now; // cerr << "now sending " << length_b << " from b to a!\n"; for (int i = 0; i < 9; i++) SendB(length_b >> i & 1); if (length_b < length) { for (int i = 0; i < 11; i++) SendB(u >> i & 1); done[u] = 1; length = cnt_length = 0; receive_length = 1; } else { receive_length = 0; pos = 0, cnt_pos = 0; } } } // namespace b void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) { b::N = N; b::adj.resize(N); b::d.assign(N, 1e9); b::done.assign(N, 0); for (int i = 0; i < B; i++) b::adj[S[i]].emplace_back(T[i], D[i]); for (int i = 0; i < B; i++) b::adj[T[i]].emplace_back(S[i], D[i]); b::pq.emplace(0, 0); b::d[0] = 0; b::done[0] = 1; b::max_until_now = 0; b::receive_length = 1; b::length = b::cnt_length = 0; } void ReceiveB(bool y) { if (b::receive_length) { b::length |= y << b::cnt_length; b::cnt_length++; if (b::cnt_length == 9) { bool ok = 1; for (int i = 0; i < b::N; i++) ok &= b::done[i]; // cerr << "now receiving length " << b::length << " from a to b\n"; while (b::pq.size()) { auto [du, u] = b::pq.top(); if (b::done[u] == 0) { b::send_nude(-du, u); ok = 1; break; } b::pq.pop(); if (-du != b::d[u]) continue; b::max_until_now = -du; for (auto&& [v, w] : b::adj[u]) { if (b::d[v] > b::d[u] + w) { b::d[v] = b::d[u] + w; b::pq.emplace(-b::d[v], v); } } } if (!ok) b::send_nude(b::max_until_now + 511, 0); } } else { b::pos |= y << b::cnt_pos; b::cnt_pos++; if (b::cnt_pos == 11) { // cerr << "now receiving pos " << b::pos << " from a to b!\n"; b::d[b::pos] = b::length + b::max_until_now; b::pq.emplace(-b::d[b::pos], b::pos); b::done[b::pos] = 1; b::receive_length = 1; b::cnt_length = b::length = 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...