Submission #578999

#	Time	Username	Problem	Language	Result	Execution time	Memory
578999		Lucpp	Two Transportations (JOI19_transportations)	C++17	62 / 100	811 ms	48800 KiB

Azer

#include "Azer.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;

namespace {

int N;
vector<vector<pair<int, int>>> g;
vector<int> dist;
vector<bool> vis;
queue<bool> received;
int curDist = 0;
int numVisited = 1;

void sendInt(int x, int bits){
  for(int i = 0; i < bits; i++){
    bool b = x & (1<<i);
    SendA(b);
  }
}

void send(){
  if(numVisited == N) return;
  numVisited++;
  int u = 0, d = INF;
  for(int i = 0; i < N; i++){
    if(!vis[i] && dist[i] < d){
      u = i;
      d = dist[i];
    }
  }
  vis[u] = true;
  for(auto [v, c] : g[u]){
    dist[v] = min(dist[v], dist[u]+c);
  }
  int x = min(d-curDist, 500);
  // cerr << "send " << u << " " << x << " " << curDist << "\n";
  sendInt(u, 11);
  sendInt(x, 9);
  curDist = d;
}

int receiveInt(int bits){
  int ans = 0;
  for(int i = 0; i < bits; i++){
    bool b = received.front(); received.pop();
    if(b) ans += (1<<i);
  }
  return ans;
}

void receive(){
  int u = receiveInt(11);
  int x = receiveInt(9);
  // cerr << "recv " << u << " " << x << " " << curDist << "\n";
  dist[u] = min(dist[u], curDist+x);
  send();
}

}  // namespace

void InitA(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::N = N;
  g.resize(N);
  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]);
  }
  dist.assign(N, INF);
  dist[0] = 0;
  vis.resize(N);
  vis[0] = true;
  for(auto [v, x] : g[0]){
    dist[v] = min(dist[v], x);
  }
}

void ReceiveA(bool x) {
  received.push(x);
  if(received.size() == 20){
    ::receive();
  }
}

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

Baijan

#include "Baijan.h"
#include <bits/stdc++.h>
using namespace std;
const int INF = 1e8;

namespace {

int N;
vector<vector<pair<int, int>>> g;
vector<int> dist;
vector<bool> vis;
queue<bool> received;
int curDist = 0;

void sendInt(int x, int bits){
  for(int i = 0; i < bits; i++){
    bool b = x & (1<<i);
    SendB(b);
  }
}

void send(){
  int u = 0, d = INF;
  for(int i = 0; i < N; i++){
    if(!vis[i] && dist[i] < d){
      u = i;
      d = dist[i];
    }
  }
  int x = min(d-curDist, 500);
  sendInt(u, 11);
  sendInt(x, 9);
}

int receiveInt(int bits){
  int ans = 0;
  for(int i = 0; i < bits; i++){
    bool b = received.front(); received.pop();
    if(b) ans += (1<<i);
  }
  return ans;
}

void receive(){
  int u = receiveInt(11);
  int x = receiveInt(9);
  dist[u] = min(dist[u], curDist+x);
  vis[u] = true;
  for(auto [v, c] : g[u]){
    dist[v] = min(dist[v], dist[u]+c);
  }
  curDist += x;
  send();
}

}  // namespace

void InitB(int N, int A, std::vector<int> U, std::vector<int> V,
           std::vector<int> C) {
  ::N = N;
  g.resize(N);
  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]);
  }
  dist.assign(N, INF);
  dist[0] = 0;
  vis.resize(N);
  vis[0] = true;
  for(auto [v, x] : g[0]){
    dist[v] = min(dist[v], x);
  }
  ::send();
}

void ReceiveB(bool x) {
  received.push(x);
  if(received.size() == 20){
    ::receive();
  }
}

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