Submission #1177827

#	Time	Username	Problem	Language	Result	Execution time	Memory
1177827		avighna	Two Transportations (JOI19_transportations)	C++20	52 / 100	614 ms	52544 KiB

Azer

#include "Azer.h"
#include <algorithm>
#include <queue>
#include <string>
#include <vector>

namespace {

std::string s;
std::vector<int> ans;
std::vector<bool> vis;
std::vector<std::vector<std::pair<int, int>>> adj;
std::priority_queue<std::pair<int, int>> pq;
int n;

int state = -1;

const int n_width = 11;
const int wt_width = 9;

int p_dist = 0;

void send(int u, int dist) {
  SendA(0); // we are sending
  for (int bt = 0; bt < n_width; ++bt) {
    SendA(!!(u & (1 << bt)));
  }
  for (int bt = 0; bt < wt_width; ++bt) {
    SendA(!!((dist - p_dist) & (1 << bt)));
  }
}

std::pair<int, int> receive() {
  std::pair<int, int> ans;
  if (s.empty() or s[0] == '0') {
    // other pq is empty
    s.clear();
    return {-int(1e9), -1};
  }
  for (int bt = 0; bt < n_width; ++bt) {
    ans.second += (1 << bt) * (s[bt + 1] - '0');
  }
  for (int bt = 0; bt < wt_width; ++bt) {
    ans.first += (1 << bt) * (s[bt + n_width + 1] - '0');
  }
  ans.first += p_dist;
  ans.first = -ans.first;
  s.clear();
  return ans;
}

} // namespace

void run_dijkstra() {
  pq.push(receive()); // guranteed to not be visited
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    if (u == -1) {
      return;
    }
    if (!vis[u]) {
      break;
    }
    pq.pop();
  }
  auto [dist, u] = pq.top();
  vis[u] = true;
  pq.pop();
  dist = -dist;
  ans[u] = std::min(ans[u], dist);
  send(u, dist);
  p_dist = dist;
  for (auto &[i, w] : adj[u]) {
    pq.push({-(dist + w), i});
    ans[i] = std::min(ans[i], dist + w);
  }
  SendA(1); // we want to receive
}

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  n = N;
  adj = std::vector<std::vector<std::pair<int, int>>>(N);
  for (int i = 0; i < A; ++i) {
    adj[U[i]].push_back({V[i], C[i]});
    adj[V[i]].push_back({U[i], C[i]});
  }
  ans = std::vector<int>(n, (1 << 30) - 1);
  vis.resize(n);
  ans[0] = 0;
  pq.push({0, 0});
  run_dijkstra();
}

void ReceiveA(bool x) {
  s.push_back(x + '0');
  if (state == -1) {
    if (!x) {
      run_dijkstra();
    } else {
      state = x;
    }
    return;
  }
  if (s.length() == n_width + wt_width + 1) {
    state = -1;
    run_dijkstra();
  }
}

std::vector<int> Answer() { return ans; }

Baijan

#include "Baijan.h"
#include <queue>
#include <string>
#include <vector>

namespace {

std::string s;
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<bool> vis;
std::priority_queue<std::pair<int, int>> pq;
int n;

int state = -1;

const int n_width = 11;
const int wt_width = 9;

int p_dist = 0;

void send_pq_top() {
  while (!pq.empty()) {
    auto [dist, u] = pq.top();
    if (!vis[u]) {
      break;
    }
    pq.pop();
  }
  if (pq.empty()) {
    SendB(0); // pq is empty, nothng exists
    return;
  }
  SendB(1); // pq is nonempty, followed by the info
  auto [dist, u] = pq.top();
  pq.pop();
  dist = -dist;
  for (int bt = 0; bt < n_width; ++bt) {
    SendB(!!(u & (1 << bt)));
  }
  for (int bt = 0; bt < wt_width; ++bt) {
    SendB(!!((dist - p_dist) & (1 << bt)));
  }
}

// receive [u, dist]
std::pair<int, int> receive() {
  std::pair<int, int> ans;
  for (int bt = 0; bt < n_width; ++bt) {
    ans.first += (1 << bt) * (s[bt] - '0');
  }
  for (int bt = 0; bt < wt_width; ++bt) {
    ans.second += (1 << bt) * (s[bt + n_width] - '0');
  }
  ans.second += p_dist;
  s.clear();
  return ans;
}

} // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  n = N;
  adj = std::vector<std::vector<std::pair<int, int>>>(N);
  for (int i = 0; i < B; ++i) {
    adj[S[i]].push_back({T[i], D[i]});
    adj[T[i]].push_back({S[i], D[i]});
  }
  vis.resize(n);
}

void ReceiveB(bool y) {
  if (state == -1) {
    if (!y) {
      // azer is sending their info
      state = 0;
    } else {
      // azer is requesting info
      send_pq_top();
    }
    return;
  }
  s.push_back(y + '0');
  if (s.length() == n_width + wt_width) {
    auto [u, dist] = receive();
    p_dist = dist;
    vis[u] = true;
    for (auto &[i, w] : adj[u]) {
      pq.push({-(dist + w), i});
    }
    state = -1;
  }
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 8
• Subtask 3: 0 / 8
• Subtask 4: 38 / 38
• Subtask 5: 14 / 14
• Subtask 6: 0 / 10
• Subtask 7: 0 / 16