Submission #1150276

#	Time	Username	Problem	Language	Result	Execution time	Memory
1150276		cot7302	Two Transportations (JOI19_transportations)	C++20	100 / 100	311 ms	49024 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;

namespace {

using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

int N, X, ff, cnt, lst, vis_cnt;

vec<int> dis;

vec<bool> vis;

priority_queue<pair<int, int>> pq;

vec<vec<pair<int, int>>> g;

void send_number(int x, int b) {
  assert(x >= 0);
  for (int i = b - 1; i >= 0; i--) {
    SendA((x >> i) & 1);
  }
}

void send_dis() {
  if (vis_cnt == N) {
    return;
  }
  while (!empty(pq) && vis[pq.top().second]) {
    pq.pop();
  }
  if (empty(pq)) {
    send_number((1 << 9) - 1, 9);
  }
  else {
    send_number(-pq.top().first - lst, 9);
  }
}

void relax(int i) {
  for (auto [to, w] : g[i]) {
    if (dis[to] > dis[i] + w) {
      pq.emplace(-(dis[to] = dis[i] + w), to);
    }
  }
}

}

void InitA(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
  ::N = N;
  g.resize(N);
  dis.resize(N, infty<int>);
  vis.resize(N, false);
  for (int i = 0; i < A; i++) {
    g[U[i]].emplace_back(V[i], C[i]);
    g[V[i]].emplace_back(U[i], C[i]);
  }
  dis[0] = 0;
  vis[0] = true;
  vis_cnt = 1;
  relax(0);
  send_dis();
}

void ReceiveA(bool f) {
  if (ff == 0) {
    if (cnt++ < 9) {
      X = X * 2 + f;
      if (cnt == 9) {
        if (!empty(pq) && -pq.top().first - lst <= X) {
          auto [d, i] = pq.top();
          d = -d;
          lst = d;
          pq.pop();
          vis[i] = true;
          vis_cnt += 1;
          relax(i);
          send_number(i, 11);
          send_dis();
        }
        else {
          ff = 1;
          lst += X;
        }
        cnt = 0;
        X = 0;
      }
    }
  }
  else {
    if (cnt++ < 11) {
      X = X * 2 + f;
      if (cnt == 11) {
        dis[X] = lst;
        vis[X] = true;
        vis_cnt += 1;
        relax(X);
        send_dis();
        ff = 0;
        cnt = 0;
        X = 0;
      }
    }
  }
}

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

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
using namespace std;

namespace {

using i64 = long long;

template <class T>
using vec = vector<T>;

template <class T>
constexpr T infty = 0;

template <>
constexpr int infty<int> = 1'000'000'000;

template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;

int N, X, ff, cnt, lst, vis_cnt;

vec<int> dis;

vec<bool> vis;

priority_queue<pair<int, int>> pq;

vec<vec<pair<int, int>>> g;

void send_number(int x, int b) {
  assert(x >= 0);
  for (int i = b - 1; i >= 0; i--) {
    SendB((x >> i) & 1);
  }
}

void send_dis() {
  if (vis_cnt == N) {
    return;
  }
  while (!empty(pq) && vis[pq.top().second]) {
    pq.pop();
  }
  if (empty(pq)) {
    send_number((1 << 9) - 1, 9);
  }
  else {
    send_number(-pq.top().first - lst, 9);
  }
}

void relax(int i) {
  for (auto [to, w] : g[i]) {
    if (dis[to] > dis[i] + w) {
      pq.emplace(-(dis[to] = dis[i] + w), to);
    }
  }
}

}

void InitB(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
  ::N = N;
  g.resize(N);
  dis.resize(N, infty<int>);
  vis.resize(N, false);
  for (int i = 0; i < A; i++) {
    g[U[i]].emplace_back(V[i], C[i]);
    g[V[i]].emplace_back(U[i], C[i]);
  }
  dis[0] = 0;
  vis[0] = true;
  vis_cnt = 1;
  relax(0);
  send_dis();
}

void ReceiveB(bool f) {
  if (ff == 0) {
    if (cnt++ < 9) {
      X = X * 2 + f;
      if (cnt == 9) {
        if (!empty(pq) && -pq.top().first - lst < X) {
          auto [d, i] = pq.top();
          d = -d;
          lst = d;
          pq.pop();
          vis[i] = true;
          vis_cnt += 1;
          relax(i);
          send_number(i, 11);
          send_dis();
        }
        else {
          ff = 1;
          lst += X;
        }
        cnt = 0;
        X = 0;
      }
    }
  }
  else {
    if (cnt++ < 11) {
      X = X * 2 + f;
      if (cnt == 11) {
        dis[X] = lst;
        vis[X] = true;
        vis_cnt += 1;
        relax(X);
        send_dis();
        ff = 0;
        cnt = 0;
        X = 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