# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1150157 | marvinthang | Two Transportations (JOI19_transportations) | C++17 | 0 ms | 0 KiB |
#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int INF = MASK(20) - 1;
int N, cnt, pu, last, pv, pdv;
vector <bool> used;
vector <int> dist;
vector <vector <pair <int, int>>> adj;
void dijkstra(int u) {
used[u] = true;
last = dist[u];
for (auto [w, v]: adj[u]) dist[v] = min(dist[v], dist[u] + w);
u = -1;
for (int i = 0; i < N; ++i) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
if (u == -1) return;
pu = u;
int x = min(dist[u] - last, 501);
for (int i = 0; i < 9; ++i) SendA(x >> i & 1);
}
} // namespace
void InitA(int N, int A, vector <int> U, vector <int> V, vector <int> C) {
::N = N;
cnt = pv = pdv = 0;
used.resize(N);
dist.assign(N, INF);
adj.resize(N);
for (int i = 0; i < A; ++i) {
adj[U[i]].emplace_back(C[i], V[i]);
adj[V[i]].emplace_back(C[i], U[i]);
}
dist[0] = 0;
dijkstra(0);
}
void ReceiveA(bool x) {
if (cnt < 9) {
if (x) pdv |= MASK(cnt);
if (++cnt == 9) {
pdv += last;
if (dist[pu] <= pdv) {
for (int i = 0; i < 11; ++i) SendA(pu >> i & 1);
dijkstra(pu);
cnt = pdv = 0;
} else pv = 0;
}
} else {
if (x) pv |= MASK(cnt - 9);
if (++cnt == 20) {
dist[pv] = min(dist[pv], pdv);
dijkstra(pv);
cnt = pdv = 0;
}
}
}
vector <int> Answer() { return dist; }
#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
const int INF = MASK(20) - 1;
int N, cnt, pu, last, pv, pdv;
vector <bool> used;
vector <int> dist;
vector <vector <pair <int, int>>> adj;
void dijkstra(int u) {
used[u] = true;
last = dist[u];
for (auto [w, v]: adj[u]) dist[v] = min(dist[v], dist[u] + w);
u = -1;
for (int i = 0; i < N; ++i) if (!used[i] && (u == -1 || dist[i] < dist[u])) u = i;
if (u == -1) return;
pu = u;
int x = min(dist[u] - last, 501);
for (int i = 0; i < 9; ++i) SendB(x >> i & 1);
}
} // namespace
void InitB(int N, int B, vector <int> S, vector <int> T, vector <int> D) {
::N = N;
cnt = pv = pdv = 0;
used.resize(N);
dist.assign(N, INF);
adj.resize(N);
for (int i = 0; i < B; ++i) {
adj[S[i]].emplace_back(D[i], T[i]);
adj[T[i]].emplace_back(D[i], S[i]);
}
dist[0] = 0;
dijkstra(0);
}
void ReceiveB(bool x) {
if (cnt < 9) {
if (x) pdv |= MASK(cnt);
if (++cnt == 9) {
pdv += last;
if (dist[pu] < pdv) {
for (int i = 0; i < 11; ++i) SendB(pu >> i & 1);
dijkstra(pu);
cnt = pdv = 0;
} else pv = 0;
}
} else {
if (x) pv |= MASK(cnt - 9);
if (++cnt == 20) {
dist[pv] = min(dist[pv], pdv);
dijkstra(pv);
cnt = pdv = 0;
}
}
}