Submission #200363

#	Time	Username	Problem	Language	Result	Execution time	Memory
200363		EntityIT	Two Transportations (JOI19_transportations)	C++14	100 / 100	1862 ms	85480 KiB

Azer

#include "Azer.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

namespace A {
  const int inf = 1e9;

  int n, a;
  vector<vector<pair<int, int> > > gr;

  int mxD;
  vector<int> d;
  int cntDone = 0;
  vector<bool> done;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

  pair<int, int> cur{};
  int dest = 9;

  void ins(int u) { pq.emplace(d[u], u); }
  int get() {
    if (!sz(pq) ) return -1;

    int ret = pq.top().second; pq.pop();
    done[ret] = true;
    mxD = d[ret];
    ++cntDone;
    while (sz(pq) && done[pq.top().second]) pq.pop();
    return ret;
  }

  int relaxingD;

  void relax(int u) {
    for (auto e : gr[u]) {
      int v = e.first, w = e.second;

      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        ins(v);
      }
    }

//    cerr << "A: ";
//    for (int i : d) cerr << i << ' ';
//    cerr << '\n';
  }

  void send(int val, int len) {
//    cerr << "A send: " << len << ' ' << val << '\n';
    for (int i = 0; i < len; ++i) SendA( (val >> i) & 1);
  }
}

void InitA(int N, int A, vector<int> U, vector<int> V,
           vector<int> C) {
  A::n = N;
  A::a = A;
  A::gr.assign(A::n, {} );
  for (int i = 0; i < A::a; ++i) {
    A::gr[ U[i] ].emplace_back(V[i], C[i]);
    A::gr[ V[i] ].emplace_back(U[i], C[i]);
  }

  A::mxD = 0;
  A::d.assign(A::n, A::inf); A::d[0] = 0;
  A::done.assign(A::n, false);
  A::ins(0);

  A::send(0, 9);
}

void ReceiveA(bool x) {
  A::cur.second |= (x << (A::cur.first++) );

  if (A::cur.first < A::dest) return ;

//  cerr << "A receive: " << A::cur.first << ' ' << A::cur.second << '\n';

  if (A::dest == 9) {
    if (A::cur.second == (1 << 9) - 1) {
      int u = A::get();
      A::send(u, 11);
      A::relax(u);

      if (A::cntDone == A::n) return ;

      if (sz(A::pq) ) {
        int tmp = A::pq.top().first - A::mxD;
        A::send(tmp, 9);
      }
      else A::send( (1 << 9) - 1, 9);
    }
    else {
      A::relaxingD = A::cur.second;
      A::dest = 11;
    }
  }
  else {
    int u = A::cur.second;
    A::mxD = A::d[u] = A::mxD + A::relaxingD; A::done[u] = true;
    while (sz(A::pq) && A::done[A::pq.top().second]) A::pq.pop();

    A::relax(u);

    ++A::cntDone;
    if (A::cntDone == A::n) return;

    if (sz(A::pq) ) {
      int tmp = A::pq.top().first - A::mxD;
      A::send(tmp, 9);
    }
    else A::send( (1 << 9) - 1, 9);
    A::dest = 9;
  }

  A::cur = {};
}

vector<int> Answer() { return A::d; }

Baijan

#include "Baijan.h"
#include<bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define sz(x) ( (int)(x).size() )
using LL = long long;

namespace B{
  const int inf = 1e9;

  int n, b;
  vector<vector<pair<int, int> > > gr;

  int mxD;
  vector<int> d;
  int cntDone = 0;
  vector<bool> done;
  priority_queue<pair<int, int>, vector<pair<int, int> >, greater<pair<int, int> > > pq;

  pair<int, int> cur{};
  int dest = 9;

  void ins(int u) { pq.emplace(d[u], u); }
  int get() {
    if (!sz(pq) ) return -1;

    int ret = pq.top().second; pq.pop();
    done[ret] = true;
    mxD = d[ret];
    ++cntDone;
    while (sz(pq) && done[pq.top().second]) pq.pop();
    return ret;
  }

  int relaxingD;

  void relax(int u) {
    for (auto e : gr[u]) {
      int v = e.first, w = e.second;

      if (d[v] > d[u] + w) {
        d[v] = d[u] + w;
        ins(v);
      }
    }

//    cerr << "B: ";
//    for (int i : d) cerr << i << ' ';
//    cerr << '\n';
  }

  void send(int val, int len) {
//    cerr << "B send: " << len << ' ' << val << '\n';
    for (int i = 0; i < len; ++i) SendB( (val >> i) & 1);
  }
}

void InitB(int N, int B, vector<int> S, vector<int> T,
           vector<int> D) {
  B::n = N;
  B::b = B;
  B::gr.assign(B::n, {} );
  for (int i = 0; i < B::b; ++i) {
    B::gr[ S[i] ].emplace_back(T[i], D[i]);
    B::gr[ T[i] ].emplace_back(S[i], D[i]);
  }

  B::mxD = 0;
  B::d.assign(B::n, B::inf); B::d[0] = 0;
  B::done.assign(B::n, false);
  B::ins(0);
}

void ReceiveB(bool y) {
  B::cur.second |= (y << (B::cur.first++) );

  if (B::cur.first < B::dest) return ;

//  cerr << "B receive: " << B::cur.first << ' ' << B::cur.second << '\n';

  if (B::dest == 9) {
    int tmp = (sz(B::pq) ? B::pq.top().first - B::mxD : (1 << 9) - 2);

    if (tmp < B::cur.second) {
      int u = B::get();
      B::relax(u);

      B::send(tmp, 9);
      B::send(u, 11);
    }
    else {
      B::relaxingD = B::cur.second;

      B::send( (1 << 9) - 1, 9);

      B::dest = 11;
    }
  }
  else {
    int u = B::cur.second;
    B::mxD = B::d[u] = B::relaxingD + B::mxD; B::done[u] = true;
    while (sz(B::pq) && B::done[B::pq.top().second]) B::pq.pop();

    B::relax(u);

    ++B::cntDone;
    if (B::cntDone == B::n) return;

    B::dest = 9;
  }

  B::cur = {};
}

• 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