| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 788172 | someone | Two Transportations (JOI19_transportations) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "transportations.hpp"
namespace Azer { // start namespace Azer
struct Arc {
int nex, pds;
};
const int N = 2e3 + 42, INF = 1e6 + 42;
bool sent[N];
int n, knows[N];
vector<bool> msg;
vector<int> dist;
vector<Arc> arc[N];
priority_queue<pair<int, int>> pq;
void Init(int X, int a, vector<int> U, vector<int> V, vector<int> C) {
n = X;
dist.resize(n);
for(int i = 0; i < a; i++) {
arc[U[i]].push_back({V[i], C[i]});
arc[V[i]].push_back({U[i], C[i]});
}
for(int i = 1; i < n; i++)
knows[i] = dist[i] = INF;
for(int i = 0; i < n; i++)
pq.push({-dist[i], i});
bool envoi = false;
while(!envoi && !pq.empty()) {
int i = pq.top().second,
d = -pq.top().first;
pq.pop();
if(dist[i] == d) {
for(Arc a : arc[i]) {
if(dist[a.nex] > dist[i] + a.pds) {
dist[a.nex] = dist[i] + a.pds;
pq.push({-dist[a.nex], a.nex});
}
}
if(!sent[i]) {
//cout << "Azer envoie " << i << ' ' << d << '\n';
sent[i] = true;
envoi = true;
for(int j = 0; j < 11; j++)
Send(i & (1 << j));
for(int j = 0; j < 20; j++)
Send(d & (1 << j));
}
}
}
}
void Receive(bool x) {
msg.push_back(x);
if(31 == (int)msg.size()) {
int i = 0, d = 0;
for(int j = 0; j < 11; j++)
i += (1 << j) * msg[j];
for(int j = 0; j < 20; j++)
d += (1 << j) * msg[j + 11];
msg.clear();
dist[i] = min(dist[i], d);
pq.push({-dist[i], i});
knows[i] = d;
bool envoi = false;
while(!envoi && !pq.empty()) {
i = pq.top().second,
d = -pq.top().first;
pq.pop();
if(dist[i] == d) {
for(Arc a : arc[i]) {
if(dist[a.nex] > dist[i] + a.pds) {
dist[a.nex] = dist[i] + a.pds;
pq.push({-dist[a.nex], a.nex});
}
}
if(!sent[i] && knows[i] > d) {
//cout << "Azer envoie " << i << ' ' << d << '\n';
knows[i] = d;
sent[i] = true;
envoi = true;
for(int j = 0; j < 11; j++)
Send(i & (1 << j));
for(int j = 0; j < 20; j++)
Send(d & (1 << j));
}
}
}
if(!envoi)
for(int j = 0; j < n; j++)
if(dist[j] == INF) {
for(int k = 0; k < 11; k++)
Send(j & (1 << k));
for(int k = 0; k < 20; k++)
Send(INF & (1 << k));
}
}
}
vector<int> Answer() {
return dist;
}
} // end namespace Azer
#include "transportations.hpp"
namespace Baijan { // start namespace Baijan
struct Arc {
int nex, pds;
};
const int N = 2e3 + 42, INF = 1e6 + 42;
bool sent[N];
int n, knows[N];
vector<int> dist;
vector<Arc> arc[N];
vector<bool> msg;
priority_queue<pair<int, int>> pq;
void Init(int X, int b, vector<int> S, vector<int> T, vector<int> D) {
n = X;
dist.resize(n);
for(int i = 0; i < b; i++) {
arc[S[i]].push_back({T[i], D[i]});
arc[T[i]].push_back({S[i], D[i]});
}
for(int i = 1; i < n; i++)
knows[i] = dist[i] = INF;
for(int i = 0; i < n; i++)
pq.push({-dist[i], i});
}
void Receive(bool y) {
msg.push_back(y);
if(31 == (int)msg.size()) {
int i = 0, d = 0;
for(int j = 0; j < 11; j++)
i += (1 << j) * msg[j];
for(int j = 0; j < 20; j++)
d += (1 << j) * msg[j + 11];
msg.clear();
dist[i] = min(dist[i], d);
pq.push({-dist[i], i});
knows[i] = d;
bool envoi = false;
while(!envoi && !pq.empty()) {
i = pq.top().second,
d = -pq.top().first;
pq.pop();
if(dist[i] == d) {
for(Arc a : arc[i]) {
if(dist[a.nex] > dist[i] + a.pds) {
dist[a.nex] = dist[i] + a.pds;
pq.push({-dist[a.nex], a.nex});
}
}
if(!sent[i] && knows[i] > d) {
knows[i] = d;
//cout << "Baijan envoie " << i << ' ' << d << '\n';
sent[i] = true;
envoi = true;
for(int j = 0; j < 11; j++)
Send(i & (1 << j));
for(int j = 0; j < 20; j++)
Send(d & (1 << j));
}
}
}
if(!envoi)
for(int j = 0; j < n; j++)
if(dist[j] == INF) {
for(int k = 0; k < 11; k++)
Send(j & (1 << k));
for(int k = 0; k < 20; k++)
Send(INF & (1 << k));
}
}
}
} // end namespace Baijan