Submission #748595

#TimeUsernameProblemLanguageResultExecution timeMemory
748595piOOETwo Transportations (JOI19_transportations)C++17
0 / 100
3000 ms656 KiB
#include "Azer.h" #include <bits/stdc++.h> using namespace std; namespace { constexpr int maxN = 2000, maxQ = 58001; constexpr int inf = 1e9 + 7; int N, A, Q = 0, S = 0, Last = 0, usedCnt = 0; vector<pair<int, int>> adj[maxN]; set<pair<int, int>> st; int dist[maxN]; bool used[maxN], b[maxQ]; void upd(int v) { for (auto [to, w]: adj[v]) { if (!used[to] && dist[to] > dist[v] + w) { st.erase({dist[to], to}); st.emplace(dist[to] = dist[v] + w, to); } } } void ckmin(int v, int d) { if (dist[v] > d) { st.erase({dist[v], v}); st.emplace(dist[v] = d, v); // upd(v); } } } void InitA(int N, int A, std::vector<int> U, std::vector<int> V, std::vector<int> C) { ::N = N, ::A = A; for (int i = 0; i < A; ++i) { adj[U[i]].emplace_back(V[i], C[i]); adj[V[i]].emplace_back(U[i], C[i]); } fill(dist, dist + N, inf); ckmin(0, 0); for (int i = 0; i < 9; ++i) { SendA(0); } } void ReceiveA(bool x) { b[Q++] = x; if (Q - Last == 9) { int nd = 0; for (int i = 0; i < 9; ++i) { nd |= b[Last + i] << i; } if (nd > 500) { auto [d, v] = *st.begin(); st.erase(st.begin()); upd(v); assert(!used[v]); used[v] = true; usedCnt += 1; S += d; for (int i = 0; i < 11; ++i) { SendA(v >> i & 1); } Last = Q; } } else if (Q - Last == 9 + 11) { int nd = 0, v = 0; for (int i = 0; i < 9; ++i) { nd |= b[Last + i] << i; } for (int i = 0; i < 11; ++i) { v |= b[Last + i + 9] << i; } assert(!used[v]); used[v] = true; usedCnt += 1; ckmin(v, S + nd); st.erase({dist[v], v}); S += nd; Last = Q; } if (Q == Last) { if (st.empty() && usedCnt == N) { return; } else if (st.empty()) { for (int i = 0; i < 9; ++i) { SendA(1); } return; } int d = st.begin()->first - S; for (int i = 0; i < 9; ++i) { SendA(d >> i & 1); } } } std::vector<int> Answer() { std::vector<int> ans(N); for (int k = 0; k < N; ++k) { ans[k] = dist[k]; } return ans; }
#include "Baijan.h" #include <bits/stdc++.h> using namespace std; namespace { constexpr int maxN = 2000, maxQ = 58000; constexpr int inf = 1e9 + 7; int N, B, Q = 0, S = 0, Last = 0; vector<pair<int, int>> adj[maxN]; set<pair<int, int>> st; int dist[maxN]; bool used[maxN], b[maxQ]; void upd(int v) { for (auto [to, w]: adj[v]) { if (!used[to] && dist[to] > dist[v] + w) { st.erase({dist[to], to}); st.emplace(dist[to] = dist[v] + w, to); } } } void ckmin(int v, int d) { if (dist[v] > d) { st.erase({dist[v], v}); st.emplace(dist[v] = d, v); // upd(v); } } } void InitB(int N, int B, std::vector<int> S, std::vector<int> T, std::vector<int> D) { ::N = N, ::B = B; fill(dist, dist + N, inf); for (int i = 0; i < B; ++i) { adj[S[i]].emplace_back(T[i], D[i]); adj[T[i]].emplace_back(S[i], D[i]); } } void ReceiveB(bool y) { b[Q++] = y; if ((Q - Last) == 9) { int d = 0; for (int i = 0; i < 9; ++i) { d |= b[Last + i] << i; } // cout << st.size() << endl; int nd = st.empty() ? inf : st.begin()->first - S; if (nd < d) { int v = st.begin()->second; st.erase(st.begin()); upd(v); assert(!used[v]); used[v] = true; // cout << "B gives: " << v << " " << S << "+" << nd << endl; for (int i = 0; i < 9; ++i) { SendB(nd >> i & 1); } for (int i = 0; i < 11; ++i) { SendB(v >> i & 1); } S += nd; Last = Q; } else { for (int i = 0; i < 9; ++i) { SendB(1); } } } else if (Q - Last == 9 + 11) { int d = 0, v = 0; for (int i = 0; i < 9; ++i) { d |= b[Last + i] << i; } for (int i = 0; i < 11; ++i) { v |= b[Last + 9 + i] << i; } ckmin(v, S + d); used[v] = true; st.erase({dist[v], v}); // cout << "B received: " << v << " " << S << "+" << d << endl; S += d; Last = Q; } }
#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...