Submission #1178115

#	Time	Username	Problem	Language	Result	Execution time	Memory
1178115		avighna	Two Transportations (JOI19_transportations)	C++20	100 / 100	369 ms	57800 KiB

Azer

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

namespace {

std::string s;

int n, prev_ans, state, d_b;
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> ans;
std::vector<bool> vis;
std::priority_queue<std::pair<int, int>> pq;

void add_paths(int u) {
  for (auto &[i, w] : adj[u]) {
    pq.push({-(ans[u] + w), i});
  }
}

std::pair<int, int> closest() {
  std::pair<int, int> p = {-1, (1 << 30) - 1};
  while (!pq.empty()) {
    auto [d, u] = pq.top();
    if (!vis[u]) {
      break;
    }
    pq.pop();
  }
  if (pq.empty()) {
    return p;
  }
  p = pq.top();
  return {p.second, -p.first};
}

void send(int x, int width) {
  // std::cout << "sending " << x << " from a" << std::endl;
  for (int i = 0; i < width; ++i) {
    SendA(!!(x & (1 << i)));
  }
}

int receive(int width) {
  int ans = 0;
  for (int i = 0; i < width; ++i) {
    ans += (1 << i) * (s[i] - '0');
  }
  s = s.substr(width, s.length());
  return ans;
}

bool compare_closest() {
  d_b = receive(9) + prev_ans;
  if (d_b == 511 + prev_ans) {
    d_b = (1 << 30) - 1;
  }
  auto [u, d] = closest();
  if (d < d_b) {
    send(d - prev_ans, 9);
    send(u, 11);
    ans[u] = d;
    add_paths(u), vis[u] = true;
    prev_ans = d;
    return false;
  } else {
    send(511, 9);
    return true;
  }
}

} // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  prev_ans = 0, state = 0, n = N;
  adj.resize(n);
  ans.resize(n, (1 << 30) - 1);
  vis.resize(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[0] = 0;
  vis[0] = true;
  add_paths(0);
}

void ReceiveA(bool x) {
  s.push_back(x + '0');
  if (state == 0 and s.length() == 9) {
    state = compare_closest();
  } else if (state == 1 and s.length() == 11) {
    int u = receive(11);
    ans[u] = d_b;
    add_paths(u), vis[u] = true;
    prev_ans = d_b;
    state = 0;
  }
}

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

Baijan

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

namespace {

std::string s;

int n, prev_ans, u_cl, d_cl, state, found;
std::vector<std::vector<std::pair<int, int>>> adj;
std::vector<int> ans;
std::vector<bool> vis;
std::priority_queue<std::pair<int, int>> pq;

void add_paths(int u) {
  for (auto &[i, w] : adj[u]) {
    pq.push({-(ans[u] + w), i});
  }
}

std::pair<int, int> closest() {
  std::pair<int, int> p = {-1, (1 << 30) - 1};
  while (!pq.empty()) {
    auto [d, u] = pq.top();
    if (!vis[u]) {
      break;
    }
    pq.pop();
  }
  if (pq.empty()) {
    return p;
  }
  p = pq.top();
  return {p.second, -p.first};
}

void send(int x, int width) {
  // std::cout << "sending " << x << " from b" << std::endl;
  for (int i = 0; i < width; ++i) {
    SendB(!!(x & (1 << i)));
  }
}

int receive(int width) {
  int ans = 0;
  for (int i = 0; i < width; ++i) {
    ans += (1 << i) * (s[i] - '0');
  }
  s = s.substr(width, s.length());
  return ans;
}

void send_closest() {
  if (found >= n) {
    return;
  }
  found++;
  auto [u, d] = closest();
  u_cl = u, d_cl = d;
  send(std::min(d_cl - prev_ans, 511), 9);
}

} // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  prev_ans = 0, state = 0, n = N, found = 1;
  adj.resize(n);
  ans.resize(n, (1 << 30) - 1);
  vis.resize(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]});
  }
  ans[0] = 0;
  vis[0] = true;
  add_paths(0);
  send_closest();
}

void ReceiveB(bool y) {
  s.push_back(y + '0');
  if (state == 0 and s.length() == 9) {
    int d = receive(9) + prev_ans;
    if (d == 511 + prev_ans) {
      send(u_cl, 11);
      ans[u_cl] = d_cl, prev_ans = d_cl;
      add_paths(u_cl), vis[u_cl] = true;
      send_closest();
    } else {
      prev_ans = d, state = 1;
    }
  } else if (state == 1 and s.length() == 11) {
    int u = receive(11);
    ans[u] = prev_ans;
    add_paths(u), vis[u] = true;
    send_closest();
    state = 0;
  }
}

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