이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#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);
upd(v);
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});
upd(v);
// cout << "B received: " << v << " " << S << "+" << d << endl;
S += d;
Last = Q;
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |