Submission #1038667

#	Time	Username	Problem	Language	Result	Execution time	Memory
1038667		abczz	Two Transportations (JOI19_transportations)	C++17	14 / 100	402 ms	20504 KiB

Azer

#include "Azer.h"
#include <vector>
#include <iostream>
#include <queue>
#include <array>
#define ll long long

using namespace std;

namespace{
  ll n, distA[2000], pwa = 0, cura = 0, sza = 0, wa = 0, va = 0, tota;
  priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pqA;
  vector <array<ll, 2>> adjA[2000];
  void sendWeightA(ll u) {
    for (int j=8; j>=0; --j) {
      if (u & (1LL<<j)) SendA(1);
      else SendA(0);
    }
  }
  void sendNodeA(ll u) {
    for (int j=10; j>=0; --j) {
      if (u & (1LL<<j)) SendA(1);
      else SendA(0);
    }
  }
  void nxA() {
    if (!tota) return;
    --tota;
    while (!pqA.empty()) {
      auto [w, u] = pqA.top();
      if (distA[u] != w) pqA.pop();
      else break;
    }
    if (!pqA.empty()) {
      auto [w, u] = pqA.top();
      wa = w-pwa, va = u;
      sendWeightA(w-pwa);
    }
    else {
      wa = (1LL<<9)-1;
      sendWeightA((1LL<<9)-1);
    }
  }
  void propA(ll u, ll w) {
    distA[u] = w;
    for (auto [v, x] : adjA[u]) {
      if (distA[v] > w+x) {
        distA[v] = w+x;
        pqA.push({w+x, v});
      }
    }
    nxA();
  }
}
void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  pwa = cura = sza = wa = va = 0, tota = N-1, n = N;
  while (!pqA.empty()) pqA.pop();
  for (int i=0; i<N; ++i) {
    distA[i] = 1e18;
    adjA[i].clear();
  }
  for (int i=0; i<A; ++i) {
    adjA[U[i]].push_back({V[i], C[i]});
    adjA[V[i]].push_back({U[i], C[i]});
  }
  distA[0] = 0;
  for (auto [v, x] : adjA[0]) {
    if (distA[v] > x) {
      distA[v] = x;
      pqA.push({x, v});
    }
  }
  nxA();
}

void ReceiveA(bool x) {
  ++sza;
  cura *= 2, cura += (ll)x;
  if (sza == 9) {
    //cout << 'A' << " " << cura << " " << wa << endl;
    if (cura >= wa) {
      sendNodeA(va);
      sza = 0;
      pwa = wa = wa + pwa;
      pqA.pop();
      propA(va, wa);
    }
    else pwa = wa = cura + pwa;
    cura = 0;
  }
  else if (sza == 20) {
    va = cura;
    propA(va, wa);
    sza = cura = 0;
  }
}

std::vector<int> Answer() {
  vector <int> F;
  for (int i=0; i<n; ++i) {
    F.push_back(distA[i]);
  }
  return F;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <iostream>
#include <queue>
#include <array>
#define ll long long

using namespace std;

namespace{
  ll distB[2000], pwb = 0, curb = 0, szb = 0, wb = 0, vb = 0, totb;
  priority_queue <array<ll, 2>, vector<array<ll, 2>>, greater<array<ll, 2>>> pqB;
  vector <array<ll, 2>> adjB[2000];
  void sendWeightB(ll u) {
    for (int j=8; j>=0; --j) {
      if (u & (1LL<<j)) SendB(1);
      else SendB(0);
    }
  }
  void sendNodeB(ll u) {
    for (int j=10; j>=0; --j) {
      if (u & (1LL<<j)) SendB(1);
      else SendB(0);
    }
  }
  void nxB() {
    if (!totb) return;
    --totb;
    while (!pqB.empty()) {
      auto [w, u] = pqB.top();
      if (distB[u] != w) pqB.pop();
      else break;
    }
    if (!pqB.empty()) {
      auto [w, u] = pqB.top();
      wb = w-pwb, vb = u;
      sendWeightB(w-pwb);
    }
    else {
      wb = (1LL<<9)-1;
      sendWeightB((1LL<<9)-1);
    }
  }
  void propB(ll u, ll w) {
    distB[u] = w;
    for (auto [v, x] : adjB[u]) {
      if (distB[v] > w+x) {
        distB[v] = w+x;
        pqB.push({w+x, v});
      }
    }
    nxB();
  }
}
void InitB(int N, int B, std::vector<int> S, std::vector<int> T,
           std::vector<int> D) {
  pwb = curb = szb = wb = vb = 0, totb = N-1;
  while (!pqB.empty()) pqB.pop();
  for (int i=0; i<N; ++i) {
    distB[i] = 1e18;
    adjB[i].clear();
  }
  for (int i=0; i<B; ++i) {
    adjB[S[i]].push_back({T[i], D[i]});
    adjB[T[i]].push_back({S[i], D[i]});
  }
  distB[0] = 0;
  for (auto [v, x] : adjB[0]) {
    if (distB[v] > x) {
      distB[v] = x;
      pqB.push({x, v});
    }
  }
  nxB();
}

void ReceiveB(bool y) {
  ++szb;
  curb *= 2, curb += (ll)y;
  if (szb == 9) {
    //cout << 'B' << " " << curb << " " << wb << endl;
    if (curb > wb) {
      sendNodeB(vb);
      szb = 0;
      pwb = wb = wb + pwb;
      pqB.pop();
      propB(vb, wb);
    }
    else pwb = wb = curb + pwb;
    curb = 0;
  }
  else if (szb == 20) {
    vb = curb;
    propB(vb, wb);
    szb = curb = 0;
  }
}

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