제출 #1150220

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1150220		cot7302	Two Transportations (JOI19_transportations)	C++20	0 / 100	151 ms	876 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;

priority_queue<pair<int, int>> pq;

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

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

void fix_pq_empty() {
  if (vis_cnt == N) {
    return;
  }
  if (empty(pq)) {
    pq.emplace(-(lst + (1 << 9) - 1), N + 1);
  }
}

}

void InitA(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
  ::N = N;
  g.resize(N);
  dis.resize(N + 2, infty<int>);
  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_cnt = 1;
  for (auto [to, w] : g[0]) {
    dis[to] = w;
    pq.emplace(-(dis[to]), to);
  }
  fix_pq_empty();
  SendA((-pq.top().first) >> 8 & 1);
}

void ReceiveA(bool x) {
  if (ff == 0) {
    if (cnt++ < 9) {
      X = X * 2 + x;
      if (cnt != 9) {
        SendA((-pq.top().first - lst) >> (9 - cnt - 1) & 1);
      }
      else {
        auto [d, i] = pq.top();
        d = -d;
        //cerr << "A " << d - lst << ' ' << X << '\n';
        if (d - lst < X) {
          pq.pop();
          vis_cnt += 1;
          lst = d;
          for (auto [to, w] : g[i]) {
            if (dis[to] > dis[i] + w) {
              pq.emplace(-(dis[to] = dis[i] + w), to);
            }
          }
          send_number(i, 11);
          while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
            pq.pop();
          }
          fix_pq_empty();
          if (!empty(pq)) {
            SendA((-pq.top().first - lst) >> 8 & 1);
          }
        }
        else {
          ff = 1;
          lst += X;  
        }
        X = 0;
        cnt = 0;
      }
    }
  }
  else {
    if (cnt++ < 11) {
      X = X * 2 + x;
      if (cnt == 11) {
        dis[X] = lst;
        vis_cnt += 1;
        for (auto [to, w] : g[X]) {
          if (dis[to] > dis[X] + w) {
            pq.emplace(-(dis[to] = dis[X] + w), to);
          }
        }
        while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
          pq.pop();
        }
        fix_pq_empty();
        if (!empty(pq)) {
          SendA((-pq.top().first - lst) >> 8 & 1);
        }
        cnt = 0;
        ff = 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;

priority_queue<pair<int, int>> pq;

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

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

void fix_pq_empty() {
  if (vis_cnt == N) {
    return;
  }
  if (empty(pq)) {
    pq.emplace(-(lst + (1 << 9) - 1), N + 1);
  }
}

}

void InitB(int N, int A, vec<int> U, vec<int> V, vec<int> C) {
  ::N = N;
  g.resize(N);
  dis.resize(N + 2, infty<int>);
  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_cnt = 1;
  for (auto [to, w] : g[0]) {
    dis[to] = w;
    pq.emplace(-(dis[to]), to);
  }
  fix_pq_empty();
}

void ReceiveB(bool x) {
  if (ff == 0) {
    if (cnt++ < 9) {
      X = X * 2 + x;
      SendB((-pq.top().first - lst) >> (9 - cnt) & 1);
      if (cnt == 9) {
        auto [d, i] = pq.top();
        d = -d;
        //cerr << "B " << d - lst << ' ' << X << '\n';
        if (d - lst < X) {
          pq.pop();
          vis_cnt += 1;
          lst = d;
          for (auto [to, w] : g[i]) {
            if (dis[to] > dis[i] + w) {
              pq.emplace(-(dis[to] = dis[i] + w), to);
            }
          }
          send_number(i, 11);
          while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
            pq.pop();
          }
          fix_pq_empty();
        }
        else {
          ff = 1;
          lst += X;  
        }
        X = 0;
        cnt = 0;
      }
    }
  }
  else {
    if (cnt++ < 11) {
      X = X * 2 + x;
      if (cnt == 11) {
        dis[X] = lst;
        vis_cnt += 1;
        for (auto [to, w] : g[X]) {
          if (dis[to] > dis[X] + w) {
            pq.emplace(-(dis[to] = dis[X] + w), to);
          }
        }
        while (!empty(pq) && -pq.top().first != dis[pq.top().second]) {
          pq.pop();
        }
        fix_pq_empty();
        cnt = 0;
        ff = 0;
        X = 0;
      }
    }
  }
}

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