# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
790078 | thimote75 | 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"
using idata = vector<int>;
using bdata = vector<bool>;
using graph = vector<vector<pair<int, int>>>;
struct Promise {
int bytes, state = 0, result = 0;
void (*func) (int);
};
struct PromiseManager {
deque<Promise*> promises;
void receive (bool b) {
if (promises.size() == 0) return ;
Promise* promise = promises.front();
promise->result += b * (1 << promise->state);
promise->state ++;
if (promise->state != promise->bytes) return ;
promise->func(promise->result);
promises.pop_front();
delete promise;
}
void add_promise (int count, void (*func) (int)) {
Promise* prom = new Promise();
prom->bytes = count;
prom->func = func;
promises.push_back(prom);
}
};
namespace Azer { // start namespace Azer
PromiseManager manager;
void run_dij_state(int node);
void run_chk_dist (int delta);
void run_chk_node (int node);
idata distances;
bdata discovered;
graph roads;
int last_distance = 0;
int local_delta = 0;
int local_node = 0;
int N;
void run_chk_node (int node) {
run_dij_state(node);
}
void run_chk_dist (int delta) {
if (delta <= local_delta) {
local_delta = delta;
manager.add_promise( 11, run_chk_node );
} else {
for (int i = 0; i <= 10; i ++)
Send(((1 << i) & local_node) != 0);
run_dij_state(local_node);
}
}
int stage = 0;
void run_dij_state (int node) {
stage ++;
distances[node] = last_distance + local_delta;
discovered[node] = true;
last_distance += local_delta;
for (const auto &road : roads[node])
distances[road.first] = min(distances[road.first], distances[node] + road.second);
pair<int, int> best_pair = { last_distance + 502, -1 };
for (int i = 0; i < N; i ++)
if (!discovered[i])
best_pair = min(best_pair, { distances[i], i });
local_delta = best_pair.first - last_distance;
local_node = best_pair.second;
if (stage >= N) return ;
for (int i = 0; i <= 8; i ++)
Send((local_delta & (1 << i)) != 0);
manager.add_promise( 9, run_chk_dist );
}
void Init (int _N, int A, idata U, idata V, idata C) {
N = _N;
distances.resize(N, 1e9);
discovered.resize(N);
roads.resize(N);
for (int i = 0; i < A; i ++) {
roads[U[i]].push_back({ V[i], C[i] });
roads[V[i]].push_back({ U[i], C[i] });
}
run_dij_state( 0 );
}
void Receive(bool x) {
manager.receive(x);
}
idata Answer() {
return distances;
}
} // end namespace Azer
#include "transportations.hpp"
using idata = vector<int>;
using bdata = vector<bool>;
using graph = vector<vector<pair<int, int>>>;
struct Promise {
int bytes, state = 0, result = 0;
void (*func) (int);
};
struct PromiseManager {
deque<Promise*> promises;
void receive (bool b) {
if (promises.size() == 0) return ;
Promise* promise = promises.front();
promise->result += b * (1 << promise->state);
promise->state ++;
if (promise->state != promise->bytes) return ;
promise->func(promise->result);
promises.pop_front();
delete promise;
}
void add_promise (int count, void (*func) (int)) {
Promise* prom = new Promise();
prom->bytes = count;
prom->func = func;
promises.push_back(prom);
}
};
namespace Baijan { // start namespace Baijan
PromiseManager manager;
void run_dij_state(int node);
void run_chk_dist (int delta);
void run_chk_node (int node);
idata distances;
bdata discovered;
graph roads;
int last_distance = 0;
int local_delta = 0;
int local_node = 0;
int N;
void run_chk_node (int node) {
run_dij_state(node);
}
void run_chk_dist (int delta) {
if (delta <= local_delta) {
local_delta = delta;
manager.add_promise( 11, run_chk_node );
} else {
for (int i = 0; i <= 10; i ++)
Send(((1 << i) & local_node) != 0);
run_dij_state(local_node);
}
}
int stage = 0;
void run_dij_state (int node) {
stage ++;
distances[node] = last_distance + local_delta;
discovered[node] = true;
last_distance += local_delta;
for (const auto &road : roads[node])
distances[road.first] = min(distances[road.first], distances[node] + road.second);
pair<int, int> best_pair = { last_distance + 502, -1 };
for (int i = 0; i < N; i ++)
if (!discovered[i])
best_pair = min(best_pair, { distances[i], i });
local_delta = best_pair.first - last_distance;
local_node = best_pair.second;
if (stage >= N) return ;
for (int i = 0; i <= 8; i ++)
Send((local_delta & (1 << i)) != 0);
manager.add_promise( 9, run_chk_dist );
}
void Init (int _N, int A, idata U, idata V, idata C) {
N = _N;
distances.resize(N, 1e9);
discovered.resize(N);
roads.resize(N);
for (int i = 0; i < A; i ++) {
roads[U[i]].push_back({ V[i], C[i] });
roads[V[i]].push_back({ U[i], C[i] });
}
run_dij_state( 0 );
}
void Receive(bool x) {
manager.receive(x);
}
idata Answer() {
return distances;
}
} // end namespace Baijan