Submission #234899

#	Time	Username	Problem	Language	Result	Execution time	Memory
234899		AlexLuchianov	Two Transportations (JOI19_transportations)	C++14	100 / 100	1814 ms	85944 KiB

Azer

#include "Azer.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <cmath>
#include <queue>
#include <iostream>

using namespace std;

namespace {
  int const nmax = 2000;
  int const inf = nmax * 500;
  int const cost_size = 9;
  int const id_size = 11;
  int global = 0;

  vector<pair<int,int>> g[1 + nmax];
  int n;
  int dist[1 + nmax], forever[1 + nmax];
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
}

namespace rec{
  int _count = 0;
  int wait;
  int curr;
  vector<int> history;
  void waitfor(int _wait){
    wait = _wait;
    _count = 0;
    curr = 0;
  }
}

void refresh(){
  while(0 < pq.size()){
    int node = pq.top().second;
    int cost = pq.top().first;
    pq.pop();
    if(cost == dist[node]){
      for(int h = 0; h < g[node].size(); h++){
        int to = g[node][h].first;
        int edge = g[node][h].second;
        if(dist[node] + edge < dist[to]){
          dist[to] = dist[node] + edge;
          pq.push({dist[to], to});
        }
      }
    }
  }
}

int best(){
  int result = -1;
  for(int i = 0;i < n; i++)
    if(forever[i] == 0)
      if(result == -1 || dist[i] < dist[result])
        result = i;
  return result;
}

void sendnumber(int val, int bits){
  if((1 << bits) <= val)
    val = (1 << bits) - 1;

  for(int i = 0; i < bits; i++)
    SendA(0 < (val & (1 << i)));
}

void InitA(int n, int m, vector<int> u, vector<int> v, vector<int> cost) {
  ::n = n;
  for(int i = 0; i < m; i++){
    g[u[i]].push_back({v[i], cost[i]});
    g[v[i]].push_back({u[i], cost[i]});
  }
  for(int i = 0;i < n; i++)
    dist[i] = inf;
  dist[0] = 0;
  pq.push({0, 0});
  refresh();

  sendnumber(dist[best()] - global, cost_size);
  rec::waitfor(cost_size);
}

void ReceiveNumber(int number, int bits){

  if(bits == cost_size){
    int id = best();
    int mine = dist[id] - global;
    if(mine <= number) {
      sendnumber(id, id_size);
      global += mine;

      forever[id] = 1;
      if(best() != -1) {
        sendnumber(dist[best()] - global, cost_size);
        rec::waitfor(cost_size);
      }
    } else
      rec::waitfor(id_size);

  } else {
    dist[number] = global + rec::history.back();
    pq.push({dist[number], number});
    forever[number] = 1;
    refresh();
    global += rec::history.back();

    if(best() != -1) {
      sendnumber(dist[best()] - global, cost_size);
      rec::waitfor(cost_size);
    }
  }
  rec::history.push_back(number);
}

void ReceiveA(bool x) {
  rec::curr |= (x<<rec::_count);
  rec::_count++;
  if(rec::wait == rec::_count)
    ReceiveNumber(rec::curr, rec::wait);
}

vector<int> Answer() {
  vector<int> ans(n);
  for (int k = 0; k < n; ++k)
    ans[k] = dist[k];
  return ans;
}

Baijan

#include "Baijan.h"
#include <vector>
#include <queue>
#include <iostream>

using namespace std;

namespace {
  int const nmax = 2000;
  int const inf = nmax * 500;
  int const cost_size = 9;
  int const id_size = 11;
  int global = 0;

  vector<pair<int,int>> g[1 + nmax];
  int n;
  int dist[1 + nmax], forever[1 + nmax];
  priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>> > pq;
}

namespace req{
  int _count = 0;
  int wait;
  int curr;
  vector<int> history;
  void waitfor(int _wait){
    wait = _wait;
    _count = 0;
    curr = 0;
  }
}

void refreshB(){
  while(0 < pq.size()){
    int node = pq.top().second;
    int cost = pq.top().first;
    pq.pop();
    if(cost == dist[node]){
      for(int h = 0; h < g[node].size(); h++){
        int to = g[node][h].first;
        int edge = g[node][h].second;
        if(dist[node] + edge < dist[to]){
          dist[to] = dist[node] + edge;
          pq.push({dist[to], to});
        }
      }
    }
  }
}

int bestB(){
  int result = -1;
  for(int i = 0;i < n; i++)
    if(forever[i] == 0)
      if(result == -1 || dist[i] < dist[result])
        result = i;
  return result;
}

void sendnumberB(int val, int bits){
  if((1 << bits) <= val)
    val = (1 << bits) - 1;
  for(int i = 0; i < bits; i++)
    SendB(0 < (val & (1 << i)));
}

void InitB(int n, int m, vector<int> u, vector<int> v, vector<int> cost) {
  ::n = n;
  for(int i = 0; i < m; i++){
    g[u[i]].push_back({v[i], cost[i]});
    g[v[i]].push_back({u[i], cost[i]});
  }
  for(int i = 0;i < n; i++)
    dist[i] = inf;
  dist[0] = 0;
  pq.push({0, 0});
  refreshB();
  req::waitfor(cost_size);
}

void ReceiveNumberB(int number, int bits){
  if(bits == cost_size){
    int id = bestB();
    int mine = dist[id] - global;
    sendnumberB(mine, cost_size);

    if(mine < number) {
      sendnumberB(id, id_size);
      global += mine;
      forever[id] = 1;
      req::waitfor(cost_size);
    } else
      req::waitfor(id_size);

  } else {
    dist[number] = global + req::history.back();
    pq.push({dist[number], number});
    forever[number] = 1;
    refreshB();
    global += req::history.back();

    req::waitfor(cost_size);
  }
  req::history.push_back(number);
}

void ReceiveB(bool x) {
  req::curr |= (x<<req::_count);
  req::_count++;
  if(req::wait == req::_count)
    ReceiveNumberB(req::curr, req::wait);
}

Compilation message (stderr)

Azer.cpp: In function 'void refresh()':
Azer.cpp:42:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[node].size(); h++){
                      ~~^~~~~~~~~~~~~~~~

Baijan.cpp: In function 'void refreshB()':
Baijan.cpp:39:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
       for(int h = 0; h < g[node].size(); h++){
                      ~~^~~~~~~~~~~~~~~~

• 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