제출 #469615

#제출 시각아이디문제언어결과실행 시간메모리
469615jhwest2Two Transportations (JOI19_transportations)C++17
6 / 100
752 ms10212 KiB
#include "Azer.h" #include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef long long lint; typedef pair<int, int> pint; namespace { const int M = 2e3 + 10, INF = 2e9 + 10; int n, Dist[M]; priority_queue<pint, vector<pint>, greater<pint>> Q; vector<pint> G[M]; int cnt = 0, last = 0, bits = 0, type = 0, rnd = 0; } void InitA(int N, int a, vector<int> U, vector<int> V, vector<int> C) { n = N; for (int i = 0; i < n; i++) Dist[i] = INF; for (int i = 0; i < a; i++) { G[U[i]].emplace_back(C[i], V[i]); G[V[i]].emplace_back(C[i], U[i]); } Dist[0] = 0; for (auto [a, b] : G[0]) { Q.emplace(a, b); } if (Q.empty()) { for (int i = 0; i < 9; i++) SendA(1); } else { auto [a, b] = Q.top(); for (int i = 0; i < 9; i++) { SendA(a >> i & 1); } } rnd = n - 1; } void ReceiveA(bool x) { if (type == 0) { if (cnt != 8) { bits |= x << cnt; cnt += 1; return; } bits |= x << cnt; if (Q.empty() || Q.top().va > last + bits) { cnt = 0; type = 2; last = last + bits; bits = 0; return; } auto [a, b] = Q.top(); Q.pop(); Dist[b] = a; last = Dist[b]; type = cnt = bits = 0; for (auto [c, d] : G[b]) { if (Dist[d] == INF) Q.emplace(last + c, d); } while (!Q.empty() && Dist[Q.top().vb] != INF) { Q.pop(); } int kth = 0; for (int i = 0; i < b; i++) { if (Dist[i] == INF) kth += 1; } for (int i = 0; rnd >> i; i++) { SendA(kth >> i & 1); } rnd -= 1; if (rnd == 0) return; int d = (Q.empty() ? 511 : Q.top().va - last); for (int i = 0; i < 9; i++) { SendA(d >> i & 1); } return; } if (rnd >> (cnt + 1)) { bits |= x << cnt; cnt += 1; return; } bits |= x << cnt; int kth = 0, b = 0; for (int i = 0; i < M; i++) if (Dist[i] == INF) { if (kth == bits) { b = i; break; } kth += 1; } Dist[b] = last; type = cnt = bits = 0; for (auto [c, d] : G[b]) { if (Dist[d] == INF) Q.emplace(last + c, d); } while (!Q.empty() && Dist[Q.top().vb] != INF) { Q.pop(); } rnd -= 1; if (rnd == 0) return; int d = (Q.empty() ? 511 : Q.top().va - last); for (int i = 0; i < 9; i++) { SendA(d >> i & 1); } } vector<int> Answer() { vector<int> ret; for (int i = 0; i < n; i++) { ret.push_back(Dist[i]); } return ret; }
#include "Baijan.h" #include <bits/stdc++.h> #define va first #define vb second using namespace std; typedef long long lint; typedef pair<int, int> pint; namespace { const int M = 2e3 + 10, INF = 2e9 + 10; int n, Dist[M]; priority_queue<pint, vector<pint>, greater<pint>> Q; vector<pint> G[M]; int cnt = 0, last = 0, bits = 0, type = 0, rnd = 0; } void InitB(int N, int b, vector<int> U, vector<int> V, vector<int> C) { n = N; for (int i = 0; i < n; i++) Dist[i] = INF; for (int i = 0; i < b; i++) { G[U[i]].emplace_back(C[i], V[i]); G[V[i]].emplace_back(C[i], U[i]); } Dist[0] = 0; for (auto [a, b] : G[0]) { Q.emplace(a, b); } if (Q.empty()) { for (int i = 0; i < 9; i++) SendB(1); } else { auto [a, b] = Q.top(); for (int i = 0; i < 9; i++) { SendB(a >> i & 1); } } rnd = n - 1; } void ReceiveB(bool x) { if (type == 0) { if (cnt != 8) { bits |= x << cnt; cnt += 1; return; } bits |= x << cnt; if (Q.empty() || Q.top().va > last + bits) { cnt = 0; type = 2; last = last + bits; bits = 0; return; } auto [a, b] = Q.top(); Q.pop(); Dist[b] = a; last = Dist[b]; type = cnt = bits = 0; for (auto [c, d] : G[b]) { if (Dist[d] == INF) Q.emplace(last + c, d); } while (!Q.empty() && Dist[Q.top().vb] != INF) { Q.pop(); } int kth = 0; for (int i = 0; i < b; i++) { if (Dist[i] == INF) kth += 1; } for (int i = 0; rnd >> i; i++) { SendB(kth >> i & 1); } rnd -= 1; if (rnd == 0) return; int d = (Q.empty() ? 511 : Q.top().va - last); for (int i = 0; i < 9; i++) { SendB(d >> i & 1); } return; } if (rnd >> (cnt + 1)) { bits |= x << cnt; cnt += 1; return; } bits |= x << cnt; int kth = 0, b = 0; for (int i = 0; i < M; i++) if (Dist[i] == INF) { if (kth == bits) { b = i; break; } kth += 1; } Dist[b] = last; type = cnt = bits = 0; for (auto [c, d] : G[b]) { if (Dist[d] == INF) Q.emplace(last + c, d); } while (!Q.empty() && Dist[Q.top().vb] != INF) { Q.pop(); } rnd -= 1; if (rnd == 0) return; int d = (Q.empty() ? 511 : Q.top().va - last); for (int i = 0; i < 9; i++) { SendB(d >> i & 1); } }
#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...