Submission #579320

#	Time	Username	Problem	Language	Result	Execution time	Memory
579320		lumibons	Two Transportations (JOI19_transportations)	C++17	100 / 100	781 ms	60536 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int n, cd = 0, ai, ad, bi, bd, d[2100];
bool v[2100];
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> e[2100];

void init(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
  n = N;
  for (int i = 0; i < n; i++)
    d[i] = 1e9;
  d[0] = 0;
  pq.emplace(0, 0);
  for (int i = 0; i < A; ++i) {
    e[U[i]].emplace_back(V[i], C[i]);
    e[V[i]].emplace_back(U[i], C[i]);
  }
}

int next() {
  while (!pq.empty()) {
    auto [nd, i] = pq.top();
    if (!v[i])
      return i;
    pq.pop();
  }
  return -1;
}

void update(int i, int nd) {
  cd = nd;
  d[i] = nd;
  v[i] = true;
  for (auto [j, c] : e[i])
    if (d[i] + c < d[j]) {
      d[j] = d[i] + c;
      pq.emplace(-d[j], j);
    }
}

int cntInt = 0, phase, bitCnt;

void startInt() {
  if (cntInt == n)
    return;
  cntInt++;
  ai = next();
  ad = ai == -1 ? 501 : d[ai] - cd;
  for (int b = 8; b >= 0; b--)
    SendA((ad >> b) & 1);
  bi = bd = 0;
  phase = 0;
  bitCnt = 0;
}

void receiveBD(bool x) {
  bd = (bd << 1) + (x ? 1 : 0);
  bitCnt++;
  if (bitCnt == 9) {
    if (ad <= bd) {
      for (int b = 10; b >= 0; b--)
        SendA((ai >> b) & 1);
      update(ai, cd + ad);
      startInt();
    } else {
      phase = 1;
      bitCnt = 0;
    }
  }
}

void receiveBI(bool x) {
  bi = (bi << 1) + (x ? 1 : 0);
  bitCnt++;
  if (bitCnt == 11) {
    update(bi, cd + bd);
    startInt();
  }
}

}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  init(N, A, U, V, C);
  startInt();
}

void ReceiveA(bool x) {
  if (phase == 0)
    receiveBD(x);
  else
    receiveBI(x);
}

std::vector<int> Answer() {
  std::vector<int> ans(n);
  for (int i = 0; i < n; i++)
    ans[i] = d[i];
  return ans;
}

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>

using namespace std;

namespace {

int n, cd = 0, ai, ad, bi, bd, d[2100];
bool v[2100];
priority_queue<pair<int, int>> pq;
vector<pair<int, int>> e[2100];

void init(int N, int A, vector<int> U, vector<int> V, vector<int> C) {
  n = N;
  for (int i = 0; i < n; i++)
    d[i] = 1e9;
  d[0] = 0;
  pq.emplace(0, 0);
  for (int i = 0; i < A; ++i) {
    e[U[i]].emplace_back(V[i], C[i]);
    e[V[i]].emplace_back(U[i], C[i]);
  }
}

int next() {
  while (!pq.empty()) {
    auto [nd, i] = pq.top();
    if (!v[i])
      return i;
    pq.pop();
  }
  return -1;
}

void update(int i, int nd) {
  cd = nd;
  d[i] = nd;
  v[i] = true;
  for (auto [j, c] : e[i])
    if (d[i] + c < d[j]) {
      d[j] = d[i] + c;
      pq.emplace(-d[j], j);
    }
}

int cntInt = 0, phase, bitCnt;

void startInt() {
  if (cntInt == n)
    return;
  cntInt++;
  ai = next();
  ad = ai == -1 ? 501 : d[ai] - cd;
  for (int b = 8; b >= 0; b--)
    SendB((ad >> b) & 1);
  bi = bd = 0;
  phase = 0;
  bitCnt = 0;
}

void receiveBD(bool x) {
  bd = (bd << 1) + (x ? 1 : 0);
  bitCnt++;
  if (bitCnt == 9) {
    if (ad < bd) {
      for (int b = 10; b >= 0; b--)
        SendB((ai >> b) & 1);
      update(ai, cd + ad);
      startInt();
    } else {
      phase = 1;
      bitCnt = 0;
    }
  }
}

void receiveBI(bool x) {
  bi = (bi << 1) + (x ? 1 : 0);
  bitCnt++;
  if (bitCnt == 11) {
    update(bi, cd + bd);
    startInt();
  }
}

}  // namespace

void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  init(N, B, S, T, D);
  startInt();
}

void ReceiveB(bool y) {
  if (phase == 0)
    receiveBD(y);
  else
    receiveBI(y);
}

• 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